sony go for it
sony go for it
q1.cpp
// 2012.2.13
// nekohand
// このプログラムはGPLに準拠します
#include
#include
namespace {
const int MonthsNum = 12;
const int DaysNumOfMonth[] =
{31,28,31, 30,31,30, 31,31,30, 31,30,31};
const int DaysNumOfMonthOfYear = 365;
const int LeapMonth = 2;
const int DaysNumOfLeapMonth = 29;
const int DaysNumOfLeapYear = 366;
}
// Input data
typedef struct Date {
int m_year;
int m_month;
int m_day;
} Date;
// Output data
typedef struct Time {
int m_hour;
int m_minute;
int m_second;
} Time;
bool IsLeapYear(int year) {
bool leap = false;
if (year%4==0) {
if (year%100==0) {
if (year%400==0) {
leap = true;
}
} else {
leap = true;
}
}
return leap;
}
// Days since January 1, regard of leap year and month.
int DaysSinceThisYear(const Date &present) {
int days = 0;
for(int month=0; month
Time Date2Time(const Date &birth, const Date &present, int lengthOfLife) {
int daysToPresent = HowManyDays(birth, present);
Date life;
life.m_year = birth.m_year + lengthOfLife;
life.m_month = birth.m_month;
life.m_day = birth.m_day; // regardless of leap day
int daysToLife = HowManyDays(birth, life) - 1;
double rate = static_cast
Time time;
int *times[3] = {&time.m_hour, &time.m_minute, &time.m_second};
const double scales[3] = {24.0, 24.0*60.0, 24.0*60.0*60.0};
for(int i=0; i<3; ++i) {
*times[i] = static_cast
rate -= static_cast
assert(rate>=0.0 && rate<1.0);
}
return time;
}
int main () {
//------
// input
Date birth, present;
std::cout << "Input birth day" << std::endl;
std::cin >> birth.m_year >> birth.m_month >> birth.m_day;
std::cout << "Input present day" << std::endl;
std::cin >> present.m_year >> present.m_month >> present.m_day;
int lengthOfLife;
std::cout << "Input length of life" << std::endl;
std::cin >> lengthOfLife;
//------------
// calculation
Time time = Date2Time(birth, present, lengthOfLife);
//-------
// output
std::cout << "Today is " << std::endl;
std::cout << "hour:" << time.m_hour << " minute:" << time.m_minute << " second:" << time.m_second;
return 0;
}
q2
// 2012.2.13
// nekohand
// このプログラムはGPLに準拠します
#include
#include
int main() {
double real;
std::cout << "Input number";
std::cin >> real;
double result = 0.0;
int i=0;
double step = 1.0/10000.0;
while(true) {
double t = step * static_cast
double delta = step * exp(-t) * pow(t, real);
if (abs(delta)<=1.0e-16) {
break;
}
result += delta;
}
std::cout << result;
return 0;
}
q3.cpp
// 2012.2.13
// nekohand
// このプログラムはGPLに準拠します
#include
#include
#include
#include
#include
// Output data
typedef struct Answer {
int m_skip;
int m_index;
bool operator < (const Answer &rhs) {
return m_skip!=rhs.m_skip ? m_skip
std::vector
const int strN = str.size();
const int keyN = key.size();
// i as skip 1 to strN-1
for(int i=1; i
std::ifstream ifs(inputFileName);
if (ifs.bad()) {
std::cout << "Error: input file open" << std::endl;
return 0;
}
std::string outputFileName;
std::cout << "Output results file name" << std::endl;
std::cin >> outputFileName;
std::ofstream ofs(outputFileName);
if (ifs.bad()) {
std::cout << "Error: output file open" << std::endl;
return 0;
}
std::string str;
ifs >> str;
std::string key;
std::cout << "Input keyword" << std::endl;
std::cin >> key;
//---------
// Proccess
std::vector
//-------
// Output
std::sort(answers.begin(), answers.end());
for(int i=0; i
TopCoder SRM 511 （初）
TopCoder初参加記念。
Rating: 1126
Div2
Lv1:Success
Lv2:Failed Sys Test
Lv3:Opened
学生時代の試験を思い出す、ほど良い緊張感。。。
Lv1,Lv2を提出して碌に見返しもせず、勢いでLv3へ行って嵌った。
まずはLv2の見直しをするべきでした。
（あ、ウサギとネコが同数の場合は2倍しなくていいんだ・・）
Lv3はちょっと厳しかった。
ビットマスク的な考え方は見えたものの、そもそも意味を取り違えてた。
時間短縮のつもりで翻訳サイトにぶちこんで和訳を流し見たら、各々のメモリに重ねていくのだと思って、適切な戦略って何!と激しく混乱。
自分でちゃんと読まないとダメですね、はい。
とまあ、初参加にして反省点が多く、実りの多い回となりました。
次の機会の目標は「丁寧にLv1, Lv2を解く」です！
Google Code Jam 2011 QR
Problem A. Bot Trust
Problem C. Candy Splitting
の二問をsmall, large共に解いての45pointsで通過。
いちおう、去年以上のスコアはとれてよかった。
ちゃんとした実装でsmallを解ければ、largeも一瞬で解けるくらいの難易度設定かな。そんな感触。
Problem B. Magicka
Problem D. GoroSort
こちらは問題文の意味が解釈できずじまい。
やばいな。
まったく、英語力が足りてない。
Round 1はどうにか突破したいけど。。
勉強 @ 任意桁と計算精度
先日の、Vanishing Numbers @ GCJ Africa and Arabia 2011について、解き方次第で正解or不正解になってしまうのがいまいち納得できず。
http://d.hatena.ne.jp/nekohand/20110301/1298985871
http://d.hatena.ne.jp/nekohand/20110302/1299073828
モヤモヤしながら、C++でMIPRという多倍長ライブラリを使ってリトライ。
http://www.mpir.org/
どうやら、勝手に任意桁演算＝必要桁精度確保と思いこんでいたようだ。
んなわけない。
必要桁って本人しか知らないし。
MIPRにしろ、Pythonにしろ、任意桁演算するときには明示的に設定しなければならない。
さもなくば、きわどい精度問題を扱う場合にデフォルト設定に翻弄されることになる。
ヒジョーに勉強になりました。
ひとり反省会してよかった。
ともかく、必要な精度を確保しておけば、速度は別にして、細かいアルゴリズムの違いによらず正解は得られる。
そうとわかれば、より実装に集中できるはず。。
これで少しはゆっくり眠れるかな〜っと。
Vanishing Numbers（再々挑戦）
C++ with MIPR
#include <iostream> #include <fstream> #include <vector> #include <algorithm> #include <stack> #include <iomanip> #include <list> #include <string> #include <sstream> #include <math.h> #include "mpir.h" using namespace std; #define WITCH (0) //#define WITCH (1) namespace { const int MAX_LEVEL = 100; const mp_bitcnt_t PREC = MAX_LEVEL*log(3.0f)/log(2.0f); } struct Num { Num(){mpf_init(num);level=0;} mpf_t num; string str; int level; }; class Sorter { public: bool operator()(const Num &lhs, const Num &rhs) const { if (lhs.level==rhs.level) return 0>=mpf_cmp(lhs.num, rhs.num); else return lhs.level<rhs.level; } }; void input_a_case(ifstream &in, vector<Num> &nums) { int num_of_nums; in >> num_of_nums; nums.reserve(num_of_nums); for(int i=0; i<num_of_nums; ++i) { Num n; in >> n.str; stringstream ss; ss << n.str; long double a; ss >> a; mpf_init_set_str(n.num, n.str.c_str(), 10); n.level = 0; nums.push_back(n); } sort(nums.begin(), nums.end(), Sorter()); } int determine_level_of_a_number(const Num &src) { int level = 0; #if WITCH mpf_t num, min, max, par; mpf_init_set(num, src.num); mpf_init_set_str(min, "0.0", 10); mpf_init_set_str(max, "1.0", 10); mpf_init_set_str(par, "3.0", 10); mpf_t lower, upper, interval; mpf_init(lower); mpf_init(upper); mpf_init(interval); while(level++<MAX_LEVEL) { mpf_sub(interval, max, min); mpf_div(interval, interval, par); mpf_add(lower, min, interval); mpf_sub(upper, max, interval); if (0>=mpf_cmp(lower, num) && 0>=mpf_cmp(num, upper)) break; if (0>=mpf_cmp(min, num) && 0>=mpf_cmp(num, lower)) mpf_set(max, lower); if (0>=mpf_cmp(num, max) && 0>=mpf_cmp(upper, num)) mpf_set(min, upper); } mpf_clear(num); mpf_clear(min); mpf_clear(max); mpf_clear(par); mpf_clear(lower); mpf_clear(upper); mpf_clear(interval); #else mpf_t num, d1, d2, d3; mpf_init_set(num, src.num); mpf_init_set_str(d1, "1.0", 10); mpf_init_set_str(d2, "2.0", 10); mpf_init_set_str(d3, "3.0", 10); while(level++<MAX_LEVEL) { mpf_mul(num, num, d3); if (0>mpf_cmp(num, d1)) continue; else if (0>=mpf_cmp(num, d2)) break; else mpf_sub(num, num, d2); } mpf_clear(num); mpf_clear(d1); mpf_clear(d2); mpf_clear(d3); #endif return level; } void solve_a_case(ifstream &in, vector<Num> &nums) { input_a_case(in, nums); for(int i=0; i<nums.size(); ++i) { nums[i].level = determine_level_of_a_number(nums[i]); } sort(nums.begin(), nums.end(), Sorter()); } void solve_all_cases(ifstream &in, ofstream &out) { int case_num = 0; in >> case_num; for(int i=0; i<case_num; i++) { vector<Num> order_of_nums; solve_a_case(in, order_of_nums); out << "Case #" << i+1 << ":" << endl; for(int i=0; i<order_of_nums.size(); ++i) { out << order_of_nums[i].str; out << endl; } } } int main() { mpf_set_default_prec(PREC); #if 0 ifstream in("in.txt"); ofstream out("out.txt"); #elif 0 ifstream in("A-small-practice.in"); ofstream out("A-small-practice_mpir.out"); #elif 1 ifstream in("A-large-practice.in"); ofstream out("A-large-practice_mpir.out"); #endif solve_all_cases(in, out); return 0; }
from decimal import Decimal, getcontext MAX_LEVEL = 100 def main(): import math getcontext().prec = int(math.log(3**MAX_LEVEL, 2)+1) src = open("A-large-practice.in", "r") dst = open("A-large-practice.out", "w") case_num = int(src.readline()) for i in range(case_num): val_num = int(src.readline()) rst = [] for j in range(val_num): n = str(src.readline()) #level = vanish1(n) level = vanish2(n) rst.append((level, n)) rst.sort() dst.write("Case #%d:\n" % (i+1)) for l, n in rst: dst.write(n) src.close() dst.close() def vanish1(num): num = Decimal(num) d1 = Decimal('1.0') d2 = Decimal('2.0') d3 = Decimal('3.0') level = 0 while level<MAX_LEVEL: num3 = num*d3 if num3<d1: num = num3 elif num3<=d2: break else: num = num3-d2 level += 1 return level def vanish2(num): num = Decimal(num) min = Decimal('0.0') max = Decimal('1.0') par = Decimal('3.0') level = 0 while level<MAX_LEVEL: interval = (max-min)/par lower = min+interval upper = max-interval if lower<=num and num<=upper: break if min<=num and num<=lower: max = lower if num<=max and upper<=num: min = upper level += 1 return level if __name__=="__main__": main()
本番ではどちらを使おうか。悩む。。
Problem C. Radio Receiver @ Online Competition Africa and Arabia 2011
Code Jam Africa 2011の本戦C問題
http://code.google.com/codejam/contest/dashboard?c=842485#s=p2
ようやく最後の一問。
長かった。。
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- -
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
Problem C. Radio Receiver
You have a radio receiver and want to receive N messages. Each message is transmitted at a predetermined time measured in seconds since the epoch.
Also each message is transmitted from a predetermined position representing the displacement in meters from the origin (you are in 1-dimensional space).
Your radio is capable of receiving any message that is transmitted no farther than D meters from your current position, where D is a nonnegative real number.
You can start at any position of your choice and move at the rate of at most one meter per second. The action of receiving a message itself takes no time.
Your task is to find the smallest D that allows you to get all messages.
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- -
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
問題C.受信機
N個のメッセージを受け取りたい。各メッセージは事前に決められた時刻・場所から発信される。
ラジオは距離D以内のすべてのメッセージを受け取れる。Dは非負の実数。
好きな位置から始められ、たかだか1m/sで移動できる。受信はノータイム。
すべてのメッセージを受け取れる最小の受信距離Dを見つけよう。
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- -
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
メッセージの発信位置・時間が整数だから、距離Dは整数か整数＋0.5、というのは当たりが付いた。
最初に実装してみた方法では、7割くらい当たるけど残りが駄目な方法だったり。
煮詰まってので、やはり、正解者の回答を解析してみる。
二分探索っぽいことをして距離の可能性を狭めていくやり方があったので、それをアレンジしてみた。
#include <iostream> #include <fstream> #include <vector> #include <algorithm> #include <stack> #include <iomanip> #include <list> #include <string> #include <sstream> #include <cassert> using namespace std; namespace { const long long ll_1e9 = static_cast<long long>(1e+9); const long long ll_1e0 = static_cast<long long>(0); } struct Message { long long position; long long time; }; class Sorter { public: bool operator()(const Message &lhs, const Message &rhs) const { return lhs.time<=rhs.time; } }; typedef vector<Message> Messages; bool try_to_receive(const Messages &messages, long double distance) { long long pre_min = ll_1e0; long long pre_max = ll_1e9*2; long long pre_time = ll_1e0; for(int i=0; i<messages.size(); ++i) { const Message &m = messages[i]; long long time_diff = m.time - pre_time; pre_time = m.time; long long new_min = m.position-distance; long long new_max = m.position+distance; if (pre_min-time_diff>new_max || new_min-time_diff>pre_max) { return false; } else { pre_min = max(pre_min-time_diff, new_min); pre_min = max(pre_min, ll_1e0); pre_min = min(pre_min, ll_1e9*2); pre_max = min(pre_max+time_diff, new_max); pre_max = max(pre_max, ll_1e0); pre_max = min(pre_max, ll_1e9*2); } } return true; } void solve_a_case(ifstream &in, long double &distance_of_receiver) { int num_of_message; in >> num_of_message; Messages messages(num_of_message); for(int i=0; i<messages.size(); ++i) { Message m; in >> m.position; in >> m.time; messages[i] = m; } sort(messages.begin(), messages.end(), Sorter()); long long lower = ll_1e0; long long upper = ll_1e9; long long center = (lower+upper)/2; while(true) { center = (lower+upper)/2; // centerで全てカバーできるか調べる bool ok = try_to_receive(messages, center); // centerでokなら、lower~centerに最適解があるはずなのでupperをcenterで上書きして再計算 if (ok) { upper = center; } // centerでngなら、center~upperに最適解があるはずなのでlowerをcenterで上書きして再計算 else { lower = center; } if (0==upper-lower) { distance_of_receiver = static_cast<long double>(center); return; } else if (1==upper-lower) { bool lower_ok = try_to_receive(messages, lower); bool half_ok = try_to_receive(messages, static_cast<long double>(lower+upper)/2.0f); // bool upper_ok = try_to_receive(messages, upper); if (lower_ok) distance_of_receiver = static_cast<long double>(lower); else if (half_ok) distance_of_receiver = static_cast<long double>(lower+upper)/2.0f; else distance_of_receiver = static_cast<long double>(upper); return; } } } void solve_all_cases(ifstream &in, ofstream &out) { int case_num = 0; in >> case_num; for(int i=0; i<case_num; i++) { long double r = 0.0f; solve_a_case(in, r); out.precision(15); out << "Case #" << i+1 << ": " << r << endl; } } int main() { #if 0 ifstream in("in.txt"); ofstream out("out.txt"); #elif 0 ifstream in("C-small-practice.in"); ofstream out("C-small-practice.out"); #elif 1 ifstream in("C-large-practice.in"); ofstream out("C-large-practice.out"); #endif solve_all_cases(in, out); return 0; }
メッセージを受け取る範囲を漸化的に表現して、ようやく理解できた。勉強なった。。
そんなわけで、コレクト。
Problem B. Battlefield @ Online Competition Africa and Arabia 2011
Code Jam Africa 2011の本戦B問題
http://code.google.com/codejam/contest/dashboard?c=842485#s=p1
問題文が難しかった。ホンヤク。
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- -
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
Problem B. Battlefield
You are playing a game where the battlefield consists of N cities and R bidirectional roads.
Your goal is to start at some city C of your choice and visit all R roads exactly once ending this trip at C.
If this is not possible you must add the minimum number of additional roads to the initial set of roads to make this trip feasible.
Please note that there might be more than one road connecting the same pair of cities and that you are allowed to add roads
between any pair of cities regardless of whether they already had roads connecting them or not as shown in the sample input/output.
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- -
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
問題B. 戦場
N個の都市とR個の道（双方向）の戦場で遊んでいる。
目的は、ある都市Cから始めてR個の道すべてを一回だけ通ってCへ戻ってくること。
不可能なら、実行可能にするために、必要最小限の道を追加すべし。
すでに繋がっている都市間にも道路は追加できるよ。
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- -
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
すぐに一筆書き絡みの問題かなという予想は付いたが、問題の正確な意味が取れず嵌まる。
さらに実装ミスでIncorrect。問題文とコードを行ったり来たり。
英語力不足で二重苦。。
1.連結都市をグループ化
2.グループ内に偶数個の道の集まる都市しかない数をカウント
3.偶数グループが2個以上なら道で数珠繋ぎにして奇数グループ化
4.全体から奇数個の道の集まる都市の数をカウント
5.奇数都市を繋ぐ道の数は奇数都市の半分
という方針。
ソース。
#include <iostream> #include <fstream> #include <vector> #include <algorithm> #include <stack> #include <iomanip> #include <list> #include <string> #include <sstream> using namespace std; struct City { City():index_of_a_group(0){} int index_of_a_group; vector<City*> cities; }; typedef vector<City> Cities; void make_a_group(City &city, int index_of_a_group) { if (0==city.index_of_a_group) { city.index_of_a_group = index_of_a_group; } else { index_of_a_group = city.index_of_a_group; } for(int i=0; i<city.cities.size(); ++i) { if (0==city.cities[i]->index_of_a_group) { city.cities[i]->index_of_a_group = index_of_a_group; make_a_group(*city.cities[i], index_of_a_group); } } } void solve_a_case(ifstream &in, int &num_of_roads_to_be_added) { // input int num_of_cities; in >> num_of_cities; Cities cities(num_of_cities); int num_of_roads; in >> num_of_roads; for(int i=0; i<num_of_roads; ++i) { int a, b; in >> a; in >> b; cities[a].cities.push_back(&(cities[b])); cities[b].cities.push_back(&(cities[a])); } // grouping int index_of_a_group = 1; for(int i=0; i<num_of_cities; ++i) { make_a_group(cities[i], index_of_a_group); index_of_a_group++; } // cities with odd int num_of_cities_with_odd = 0; for(int i=0; i<num_of_cities; ++i) { if (1==cities[i].cities.size()%2) { num_of_cities_with_odd++; } } // unicursal group int num_of_unicursal_group = 0; for(int i=0; i<=index_of_a_group; ++i) { bool ok = true; bool ok2 = false; for(int j=0; j<cities.size(); ++j) { if (i==cities[j].index_of_a_group) { ok2 = true; if (0==cities[j].cities.size() || 1==cities[j].cities.size()%2) { ok = false; break; } } } if (ok && ok2) num_of_unicursal_group++; } // determination if (2<=num_of_unicursal_group) { num_of_roads_to_be_added = (num_of_cities_with_odd+2)/2+num_of_unicursal_group-1; } else if (1==num_of_unicursal_group) { if (0==num_of_cities_with_odd) num_of_roads_to_be_added = 0; else num_of_roads_to_be_added = num_of_cities_with_odd/2+1; } else { num_of_roads_to_be_added = num_of_cities_with_odd/2; } } void solve_all_cases(ifstream &in, ofstream &out) { int case_num = 0; in >> case_num; for(int i=0; i<case_num; i++) { int r = -1; solve_a_case(in, r); out << "Case #" << i+1 << ": " << r << endl; } } int main() { #if 0 ifstream in("in.txt"); ofstream out("out.txt"); #elif 0 ifstream in("B-small-practice.in"); ofstream out("B-small-practice.out"); #elif 1 ifstream in("B-large-practice.in"); ofstream out("B-large-practice.out"); #endif solve_all_cases(in, out); return 0; }
非常に汚いコードになってしまってるので反省。
なんとかコレクト。
