hotpepsiの練習帳

SRM 511 Div2

14:16

だいぶ遅滞

Easy (250) GameOfLifeDivTwo

問題

• ライフゲーム
• Tターン経過後の状態を返す

方針

• 二つの配列をスイッチング
• それぞれのマスで2以上なら'1'

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_511/GameOfLifeDivTwo.cpp

Medium (500) Zoo

問題

• 2種類の動物がいる
• 同じ種類で背が高いやつの数を答える
• 個々の要素がどちらの種類なのかは不明
• 組み合わせの数を答える

方針

• 2種類いる場合は、途中まで同じ数字が2回出てくるので、その重複個数nを数える
• 種類を入れ替えた場合を考慮して2^(n+1)の組み合わせ
• nが総数の1/2のときは2^nになる

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_511/Zoo.cpp

Hard (1000) FiveHundredEleven

問題

• カードを交互に出す
• カードが出せないか、出して論理和が511になったら負け
• 最適戦略でどちらが勝つか回答

方針

• とりあえず全探索

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_511/FiveHundredEleven.cpp

結果

ox- 195.58+263.97*0 1003 -> 990

mediumは場合わけができていなくてsystem test fail。まあexampleが通るところまで書けたのはよかった。

hardはとりあえずTLEするコードだけ書いた段階。

あとで解く。解いた

advisoryを読んだ。

• memoryの値が重要で、出した順番は問わない。また、何を出したらよいかもmemoryに依存するので、ターン数とmemoryを保持していれば十分
• 出したら値が変わるカード(すなわち今のmemoryにはないbitを持つカード)を出したときに必勝であるかどうがわかればよい
• そうでない場合は、残り全部が値が変わらないカードなのでカード枚数だけ進めて判定する