Google Code Jam 2010 - Qualification Round

初参加です。競技系のコンテストは2年ぶり。前はガッツリICPCとか少〜しTopCoderとかしてたくらい。

予選参加のためのエントリー資格検定試験みたいなやつ(笑)なので、レベルはそんなに高くないらしい。まぁ通ればいいやくらいのノリ。

A. Snapper Chain

いきなり問題がややこしくてよくわからん。詳細な例が少なすぎる。この問題の目的はプログラミング力ではなく英語力チェックだと思う(笑)。
各トグルスイッチのオン・オフが二進数のインクリメントと同じっぽい、と少し自信がなかったけど勝手に決めつけて解いた。K の下位 N ビットが全て1なら“ON”ってのを↓みたいに素直にコーディング。

int mask = (1<<N)-1;
bool ans = (K&mask)^mask==0;

後でトップの人のコードを見たら

bool ans = (K+1)%(1<<N)==0;

って書いてあって、「あぁそうか、、、頭いいなぁ」と思った(笑)。せめてmaskを右辺に持っていってXORは消すべきやね。要精進。

C. Theme Park

正解率が高かったので先にCに着手。ジェットコースターに何度もグループ客が乗りにくるので、一日で幾ら稼げるか計算しろと言う問題。
どう見ても環状配列。ただし、コースターの運行回数が 10^8(1億) なので下手に作るとTLE必至。とはいえ、計算可能なパターン数の目安が 10^7(1000万)ってのを考えれば、ループ内を極限まで軽くすれば1億くらい回り切るんじゃないかと予想。遷移先と稼ぎをあらかじめ計算しておいて、ループ内を2行(加算とテーブル参照)で済ます実装にした。で、Largeサイズでも十分イケた。
がしかし、LargeでWA。凡ミスかなぁ。オーバーフローとかあまり入念に考えてなかったけど、そのあたりか。。。よう分からん。

B. Fair Warning

問題文に「64bitじゃ足らんぜ」と書いてあったので、その時点で萎えまくり。Largeのサイズも50桁とかだし。
差分がTの倍数になるはずで、差のGCDから求めるんだろうなーと推測。Euclidの互除法なら50桁くらい余裕(最悪250回?)だし。・・・しかし多倍長整数の減算・剰余(減算で代用できるがその場合のオーダーはいくつだろう・・・)の実装を考えると萎え萎え。ちょっとここらへん知識も不足。
・・・結局夕方から飲み会の予定で、その後急遽カラオケになってしまったので、帰宅後爆睡でそのまま解きませんでした(爆)。

むすび

結局、結果は Small×2、Large×1 でした。順位は4000ちょっとくらい。ダメダメすぎるww。次の予選は3000人に絞られるって聞いたので、要精進だなぁ。
・・・んで、これって通過してるかどうかってどうやったら分かるの??。