Yak!の日記: Google Code Jam Round 1 参加メモ
遅くなったがとりあえず参加メモ。次記事に書くつもりのコードが思っていたより大変だったのが遅れた理由の一つだったりするのだが。
Round 1A は Rank: 1267 Score: 23 で敗退。Round 1B で Rank: 521 Score: 70 で通過した。順当に行けば次で終了な感じだが、やるだけやってみるつもりでいる。
以下、各問題について。なお、submit 済みのコードは公式 ranklist からとれるので特に上げていない。
R1A-A Rotate
とりあえず書くだけ。なのだが斜め方向のスキャンでちょっと苦労。落ち着いてちゃんと考えてからコードを書けってことで急がば回れの逆を行っている。
R1A-B Make it Smooth
R1A-Cとどっち解くかでフラフラしちゃったのが敗因の一つかと。small だけで書けないかと思ったのだがそこまで簡単じゃなかった。後から書いたコードはこちら。lib.hpp から使っているのは absdiff() のみで差の絶対値なので a<b ? b-a : a-b である。
R1A-C Number Game
小さなDPによる結果を Excel に取り込んで眺めてみて閾値があることは分かったのだがその値が分からず。黄金比だったとは。閾値を求める方向の DP で解いたコードはこちら。矩形領域から最終結果を求めるところ(calc() 周り)がもう少し簡単にならんかという気がする。本番だと間違えそうだ。
R1B-A File Fix-it
書くだけ。慣れない Boost String Algorithms のリファレンスを見ながら途中まで書いてから「いや、Perl で書いた方が早かったんじゃね?」と思いつつそのまま C++ で実装。あえて Boost 多用して書いてみたコードは次の記事で。
R1B-B Picking Up Chicks
Contest Analysis を読めば分かるが、とりあえず交換できるのは一度に二匹のみというのがミソで全体の事を考えずとも前方にいる奴らが barn に到達できない場合のみそしてその時のみ交換する必要がある。時間中だと不要に O(n^2) で書いてしまった(Step3 に対する考察が甘かった)が Contest Analysis 通り O(n) で書ける。あえて Boost 多用して書いてみたコードは次の記事で。
R1B-C Your Rank is Pure
問題の意味が分からんという人が結構いたようで。
When n is given, in how many ways you can pick S, a subset of {2, 3, ..., n}, so that n is pure, with respect to S?
という一文に圧縮されてしまっているのが分かりにくさの一因だろうか。{ 2, 3, ..., n } の部分集合のうち n が pure になるものがいくつあるか、という問題なのだが。
で、Contest Analysis に書いてあるほぼそのままのアルゴリズムだったのだが large で落ちた。組み合わせ(nCr)の modulo の取り方をミスっていた。
ULL result = 1;
for(UI i = 1; i <=r; ++i) {
result = (result * n / i) % 100003ULL;
--n;
}
ベースは割れるだけ割るようにしてオーバーフローしないように組み合わせを求めるコードなのだがそれぞれのステップで n / i が整数になると限らないので各ステップで modulo を取ってはいけない(なお modulo 取らなきゃ result * n / i は常に整数)。で、こんなコードに修正する事で通った。nCr = n-1Cr-1+n-1Cr で有ることを利用している。
const int LIM = 501;
UI comb(UI n, UI r)
{
static bool ctable_[LIM][LIM];
static UI ctable[LIM][LIM];
if(n < 0 || r > n || r < 0) return 0;
if(n == 0 || r == 0 || n == r) return 1;
if(r == 1) return n;
if(r > n - r) r = n - r;
if(ctable_[n][r]) return ctable[n][r];
UI result = (comb(n-1,r-1) + comb(n-1,r)) % 100003U;
ctable[n][r] = result; ctable_[n][r] = true;
return result;
}
全体コードはこちら
Google Code Jam Round 1 参加メモ More ログイン