Google Code JamのQualification Roundに参加しました!
Google Code Jam(GCJ)とはGoogleが主催するプログラミングの大会です。
http://code.google.com/codejam/contest/
今回行われたQualification Roundの問題一覧はこちらです。
私はProblem AとProblem Bを解いて、50ptで無事Qualificationを通過できました。
Problem Cは解き方を思いつかず、途中で諦めてしまいました。
もっと精進します。
約1〜2週間後に次のRound 1があるので、そちらでも勝ち残れるよう頑張りたいと思います。
ちなみに私の登録名はmickey24で、順位は1649位でした。
Qualification Roundなので順位は関係なく、25pt以上取れた人は全員次のRound 1に進めます。
以下、Problem AとProblem Bで私が書いたソースコード(C++)です。
興味のある方はどうぞ。
Problem A: Saving the Universe
簡単なDP(動的計画法)で解きました。
これくらいのコードをさらっと書ければ十分でしょうか。
A.cpp
#include <iostream> #include <algorithm> #include <string> using namespace std; int main() { int N; cin >> N; string t; for (int a = 1; a <= N; a++) { int s; cin >> s; getline(cin, t); string se[s]; for (int i = 0; i < s; i++) { getline(cin, se[i]); } int q; cin >> q; getline(cin, t); int sw[s][q+1]; fill(&sw[0][0], &sw[s-1][q]+1, 0); for (int i = q-1; i >= 0; i--) { getline(cin, t); for (int j = 0; j < s; j++) { if (se[j] == t) { sw[j][i] = INT_MAX; for (int k = 0; k < s; k++) { if (j != k) { sw[j][i] = min(sw[j][i], sw[k][i+1] + 1); } } } else { sw[j][i] = sw[j][i+1]; } } } int ans = INT_MAX; for (int i = 0; i < s; i++) { ans = min(sw[i][0], ans); } cout << "Case #" << a << ": " << ans << endl; } return 0; }
Problem B: Train Timetable
ちょっと長いです。
電車の発車(FROM)、到着(TO)、turnaround完了(READY)ごとにevent構造体のインスタンスを作り、それを時刻でソートして早い時刻のイベントから処理しています。
FROMイベントが来るたびに必要な電車の数をインクリメントし、READYイベントで電車が補充された時はデクリメントしています。
ちなみに、最初にソースを作成したときはeventのインスタンスをmultiset
あと、Correctで通した後に、TOイベントとREADYイベントは統合してもよかったことに気付きました。
まだまだですね。
B.cpp
#include <iostream> #include <algorithm> #include <string> #include <set> using namespace std; const int TO_A = 0; const int TO_B = 1; const int READY_A = 2; const int READY_B = 3; const int FROM_A = 4; const int FROM_B = 5; struct event { int type; int min; int param; event(int type, int min, int param = 0) : type(type), min(min), param(param) {} bool operator <(const event &rhs) const { if (min != rhs.min) { return min < rhs.min; } if (type != rhs.type) { return type < rhs.type; } return param < rhs.param; } }; int tomin(const string &t) { int m = 0; m += (t[0]-'0')*600; m += (t[1]-'0')*60; m += (t[3]-'0')*10; m += (t[4]-'0')*1; return m; } int main() { int N; cin >> N; for (int a = 1; a <= N; a++) { int t; cin >> t; int na, nb; cin >> na >> nb; multiset<event> que; for (int i = 0; i < na; i++) { string s1, s2; cin >> s1 >> s2; que.insert(event(FROM_A, tomin(s1), tomin(s2))); } for (int i = 0; i < nb; i++) { string s1, s2; cin >> s1 >> s2; que.insert(event(FROM_B, tomin(s1), tomin(s2))); } int train_a = 0; int train_b = 0; int max_train_a = 0; int max_train_b = 0; while (!que.empty()) { event e = *que.begin(); que.erase(que.begin()); switch (e.type) { case READY_A: train_a--; break; case READY_B: train_b--; break; case FROM_A: que.insert(event(TO_B, e.param)); max_train_a = max(++train_a, max_train_a); break; case FROM_B: que.insert(event(TO_A, e.param)); max_train_b = max(++train_b, max_train_b); break; case TO_A: que.insert(event(READY_A, e.min + t)); break; case TO_B: que.insert(event(READY_B, e.min + t)); break; } } cout << "Case #" << a << ": " << max_train_a << " " << max_train_b << endl; } return 0; }
Problem Cは後で解いてみようと思います。