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での勝ち抜けを目指します。

コメント

僕の場合

ちなみに、Aの問題ですが、

すこし計算してみたら、
 (K回後のSnappersのON/OFF) = (Kを2進数で表した形)
 全点灯==(111....1)
でした。
なので、
(2^K)==(0xfff..ff)==(2^N)-1
としました。

アルゴリズム本については、次が良さそうです。
・C言語による最新アルゴリズム事典 http://www.amazon.co.jp/dp/4874084141
・アルゴリズムC++ http://www.amazon.co.jp/gp/product/4764902222

Code jamには前者が良さそうです。Gcd(a,b,c)の計算も書いてあった。
ただ、前者は五十音順。分野ごとのカテゴリが欲しいところ。
後者は計算幾何とか、もう少し応用の際に役立ちそうな本です。

僕も予習します。

  • 2010/05/12(水) 18:45:48 |
  • URL |
  • やす #-
  • [ 編集 ]

すみません、間違えてました。

誤: (2^K)==(0xfff..ff)==(2^N)-1
正:     K==(0xfff..ff)==(2^N)-1

  • 2010/05/12(水) 18:57:23 |
  • URL |
  • やす #-
  • [ 編集 ]

Re: 僕の場合

 短時間もののプログラミングコンテストでは,グラフの探索や動的計画法が頻出です。
それぞれ,次の本が良いように思います。
・グラフ
  アルゴリズムクイックリファレンス : 実践的
  新訳 データ構造とネットワークアルゴリズム : 理論的
・動的計画法
  これなら分かる最適化数学 : 理論的

また,動的計画法はプログラムコンテスト上位常連のiwiさんの解説が実践的で分かりやすいと思います。
  http://d.hatena.ne.jp/iwiwi/20100328/1269790390

Code Jam Round1では必ず出題されると思いますので,この辺りを確認しておいた方が良いでしょう。
お互い頑張りましょう!

  • 2010/05/14(金) 07:46:30 |
  • URL |
  • msiro #-
  • [ 編集 ]

僕もネットワーク系(グラフ理論)、数論・組合せ系が苦手。
「データ構造とネットワークアルゴリズム」は、何故かちょうど先月、本屋で衝動買いしてしまいました。
ただ、読んでません。。。^^;

動的計画法は、画像系、テキスト解析、ゲノム解析とか、色々な場面で出てきますね。
メモリをどこまで使うべきか、悩みます。

  • 2010/05/14(金) 16:50:55 |
  • URL |
  • やす #-
  • [ 編集 ]

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://msirocoder.blog35.fc2.com/tb.php/52-2f1f0c63
この記事にトラックバックする(FC2ブログユーザー)

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