hotpepsiの練習帳

Google Code Jam 2014 Round1A

01:29

A. Charging Chaos (8pts/17pts)

問題

• 充電の特性が全て異なるN個のデバイスと、N個のコンセントがある
• それぞれの特性値が長さLの2進数で表される
• コンセントの特性値の任意のビットを反転できる
• 同じ特性値のデバイスだけが充電可能
• 全てのデバイスを充電できるようにするために反転させるビット数の最小値を求める

方針

• largeは最大40bitsなので全ての組み合わせは試せなさそう
• 半分の20bitsなら全部試せる
• 半分全列挙かな?
• がんばって書く
• Passed System Test
• (終了後)
• 任意のデバイスとコンセントを固定すれば、ビットパターンが決まり、あとは残りのコンセントに反転ビットを適用した値がデバイスに存在するか調べるだけ
• https://github.com/firewood/topcoder/blob/master/gcj_2014/R1A_A.cpp

B. Full Binary Tree (9pts/21pts)

問題

• グラフが与えられる
• どれかのノードを親として、いくつかのノードを削除して完全二分木にする
• 削除する最少数を求める

方針

• smallは残すかどうかをビットで全列挙してDFSでいける
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/gcj_2014/R1A_B.cpp

結果

ooo--- 8 + 17 + 9 = 34pts 1601st/3621

毎年のことながら1000位のゲームバランス設定がすごい。