Hatena::Grouptopcoder

tsubosakaの日記

2010-06-06

Google Code Jam Round 2

23:36

475位でぎりぎり通過

A

問題の意味を何となく理解。

ダイアモンドの大きさは2倍程度にしかならなそうなのでk <= K <= 2kぐらいの範囲のKでダイアモンドを含む図形が成立するか試せば良さそう。

実装が重そうだったので次へ

B

Smallの制約がどう効いてくるのかいまいち不明。Stat見るとC Smallを解いてる人が多かったのでそっちへ

C

ライフゲーム。左と上が生きてないと生成が起きないので盤面の外側にセルがはみ出すことはない。左上からどんどん消えてくので100ターンぐらいで終わるはず。

愚直なシミュレートを書いたところ通る。

B

Mの値をいろいろ変えたときにどうなるか紙の上でいろいろと計算する。図の絵をひっくり返したrooted treeを考えたときに自分の親のノードのチケットを何個パスしたかが分かれば、その子ノードであとなんかいパスしてよいかが分かるので、現在のノードの位置と親ノードでチケットを買わなかった回数を状態とすれば状態は2^P P個しかないのでメモ化再帰で解ける。

D

図をみただけでやる気をなくす

A

とりあえず書いたけど通らない。終了間際に入力を左詰めしてたけどそれだと題意を満たさないことに気づく、修正を試みるも間に合わず。

終了時には520位台だったので終わったと思ったけどSystem testでLargeが何人か落ちたため、Round 3へ行けた。