Coding Memorandum

プログラミングに関する備忘録

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Google Code Jam 2010 Qualification Round

Google Code Jam への参加も2回目となり,だいぶ手馴れた感があります。Code Jam用のC++スケルトンコードも熟れてきました。

今回は予選ということで手を抜いてメモを取らずに頭の中で考えることとしたら,条件の考慮の抜け漏れが出てしまい,正解へ辿り着くまでに何回かのチャレンジを必要としてしまいました。英語を読み進めることに必死となり,読み取った条件が頭の中から抜けていってしまう傾向があるようです。次回のラウンドからは,しっかりとメモ上で検討を進めようと思います。

問題A

問題Aは,問題文の解釈に時間を取られました。初めは,Snapperがlightの機能を持っていると思い込んでしまい,問題文の解釈に苦しみました… "The light is plugged into the Nth Snapper"が目に入ってこなかったようです。
私の採った解法は,まずN番目のSnapperが初めてONになるまでを考えました。NがONになるには,n番目(1<=n<=N)がONになる必要があり,n番目がONになるには,n-1番目がONになってから2^(n-1)回のsnapが必要です。すなわちΣ 2^(n-1)回となります。そしてN番目のSnapperが一度ONとなった後に再度ONとなるのは,2^N 回後となります。こんな考えで実装してみました。
後ほど,2chに「1行で書ける」とあったので考え直してみたら,Σ 2^(n-1) = 2^N-1であり,そこから2^N回毎ということは,「snap回数 % 2^N = 2^N-1」が成立すればよいことに気づきました。

問題B

問題Bは,数学的なひらめきが必要そうでしたがすぐにひらめかず,またlongを解くには多倍長演算が必要であったので,パスしました。多倍長演算は「プログラミングコンテストの数学」の中で準備しておこうと思っていたのですが,面倒になって後回しとしていました。こんなことなら確認しておけば良かったと・・・

問題C

問題Cは,ローラーコースターの乗車をR回試行すれば良さそうですが,愚直に毎回乗れる人数を算出すると時間切れになりそうなので一工夫必要です。乗れる人数は,どのグループが先頭になるかで決定的な値となるため事前に計算しておきます。このようにすれば試行ループの内側は配列参照と加算で済み,ループ回数Rの最大値は10^8なので,十分に間に合います。

Round1-Aは,5/22(土) 10:00 から。今年はなるべく早いRoundでの勝ち抜けを目指します。

スポンサーサイト

FC2Ad

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。