TopCoder は半年ぐらい前に登録して、一度 Practice をやってみたまま、なんとなく時間が合わなくて放置してました。この半年の間に競技プログラマな人といっぱい知り合い、ロジックの引き出しがケタ違いでコーディングが尋常じゃなく速いことを知って、これはやった方がいいと強く思うようになりました。
というわけで TopCoder デビューです。今日は予定が空いていたので、遅くなってもいいだろうと昨晩挑戦してみました。
- AdditionGame (250): 8m36s, 229.67pts
- FoxSequence (500): 20m37s, 349.38pts
- NinePuzzle (950): 29m50s, 542.55pts
- Challenge: 50pts (FoxSequence x 1)
AdditionGame はコーディング遅いなあという感想しかないです。訓練あるのみ。
class AdditionGame { public: int getMaximumPoints(int A, int B, int C, int N) { int res = 0; do { if (A > B) { if (A > C) { res += A--; } else { res += C--; } } else if (B > C) { res += B--; } else { res += C--; } } while (--N && A + B + C); return res; } };
FoxSequence は速く書かなきゃと思って地味に地道なコードを書きました。見づらい。本当は階差数列をつくって unique して正負を見るのが一番簡単らしいですが、思いつきませんでした……
#include ... using namespace std; class FoxSequence { public: pairgetArith(const vector<int>& seq, int from) { const int end = seq.size() - 1; if (from >= end) return make_pair(-1, -1); int d = seq[from + 1] - seq[from]; if (from == end - 1) return make_pair(from + 1, d); do { ++from; } while (from < end && seq[from + 1] - seq[from] == d); return make_pair(from, d); } string isValid(vector <int> seq) { if (seq.size() < 5) return "NO"; pair<int, int> r1 = getArith(seq, 0); if (r1.first == -1 || r1.second <= 0) return "NO"; pair<int, int> r2 = getArith(seq, r1.first); if (r2.first == -1 || r2.second >= 0) return "NO"; pair<int, int> r3 = getArith(seq, r2.first); if (r3.first == -1) return "NO"; int next = r3.second ? r2.first : r3.first; pair<int, int> r4 = getArith(seq, next); if (r4.first == -1 || r4.second <= 0) return "NO"; pair<int, int> r5 = getArith(seq, r4.first); if (r5.first == -1 || r5.first != seq.size() - 1 || r5.second >= 0) return "NO"; return "YES"; } };
NinePuzzle は一筋縄では行かなさそう。しばらく思考停止してて、いやいや絶対楽する方法があるだろと図をいろいろ描いてみると、任意のペアを入れ替える操作列が必ず存在することが示せたので、ただ色が何個揃ってるか数えるだけでよしという結論。でも思いつくのに時間かかりすぎで、地道に探索書いた人より遅かったりしてて(´・ω・`)
#include ... using namespace std; class NinePuzzle { public: static int countChar(const string& str, char ch) { int cnt = 0; for (size_t i = 0; i < str.size(); ++i) { if (str[i] == ch) ++cnt; } return cnt; } static void countRGBY(const string& str, vector<int>* v) { v->clear(); v->push_back(countChar(str, 'R')); v->push_back(countChar(str, 'G')); v->push_back(countChar(str, 'B')); v->push_back(countChar(str, 'Y')); } int getMinimumCost(string init, string goal) { vector<int> iv, gv; countRGBY(init, &iv); countRGBY(goal, &gv); int match = 0; for (size_t i = 0; i < iv.size(); ++i) { match += min(iv[i], gv[i]); } return 9 - match; } };
いろいろ勉強になりました。結果は 1171.60pts でレーティング 1461 の青色。次の回は Div1 がんばります。