hotpepsiの練習帳

Google Code Jam Japan 2011

00:27

練習問題

A 数珠繋ぎ (Snapper)

• 2進数
• 最後の状態が 2^n - 1 になっているかどうか調べる
• こんな単純なのでいいのか? と思うけど通ってるっぽい。
• https://github.com/firewood/topcoder/blob/master/gcjj_2011/ex_A_snapper.cpp

B 数の集合

• 素数を生成しておく
• union find木にどんどん突っ込む
• rootになっている要素を数える
• https://github.com/firewood/topcoder/blob/master/gcjj_2011/ex_B_set.cpp

C 遊園地

• 次のグループが乗れなくなったら出発
• からっぽの状態から、乗せ始めるグループが既知であれば、ループしているのでまとめて加算
• https://github.com/firewood/topcoder/blob/master/gcjj_2011/ex_C_roller_coaster.cpp

予選

A カードシャッフル

• 逆順からシミュレーション
• https://github.com/firewood/topcoder/blob/master/gcjj_2011/QR_A_card_shuffle.cpp

B 最高のコーヒー

• 賞味期限が長い順にソート
• 賞味期限が最も長いもののうち、最も満足度が高いものを消費
• 消費する区間の長さは、対象のコーヒーの在庫終了と、別のコーヒーの賞味期限の終わりの短いほう
• https://github.com/firewood/topcoder/blob/master/gcjj_2011/QR_B_coffee.cpp

C ビット数

• 数NをAとBに分割
• 下から見ていく
• 1だったらそのまま(該当する桁はAが1でBが0)
• 0だったら1引くことにより、AとBが両方1になるので結果が2増える
• Mi_Sawaさんのソースを見て書き直した
• https://github.com/firewood/topcoder/blob/master/gcjj_2011/QR_C_bits.cpp

決勝

A アンテナ修復

• 面積が最大となる並べ方
• smallはnext_permutationでgreedyに通した
• largeは大きい順にソートして、双方向にのびていくように並べた
• 気がつかなかったが、円に近づければよいとのこと
• https://github.com/firewood/topcoder/blob/master/gcjj_2011/A_antenna.cpp

B バクテリアの増殖

• kusanoさんの回答を読んでsmallかつPythonの短さに衝撃を受ける
• smallのみをOpenSSLを使って愚直に実装してみた
• https://github.com/firewood/topcoder/blob/master/gcjj_2011/B_bacteria.cpp

結果

練習→予選→決勝に参加。

予選はAとCのlargeが通って36pt、266位で通過。

決勝はAのみlargeまで通って15pt、195位。

感想

もしかしてTシャツもらえるんだろうか。嬉しい!

練習問題の遊園地はGCJ勉強会でもやった。今回解きなおして、前より少しだけシンプルに書けたかなと思う。

予選はCがそこそこ速く解けたのは良かった。Bは終わった後だいぶかかってしまったがようやく内容を理解した。

決勝はAが通せたのは参加したかいがあった。Bは他の方の解説を読んだがまだ理解できてない。最近ガロアの本とか読んでるがまったく身についてなくて反省。素養がないので地道にやるしかない感じ。