Hatena::Grouptopcoder

hotpepsiの練習帳

2011-09-25

SRM 511 Div2

14:16

だいぶ遅滞

Easy (250) GameOfLifeDivTwo

問題

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

方針

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

実装

Medium (500) Zoo

問題

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

方針

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

実装

Hard (1000) FiveHundredEleven

問題

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

方針

  • とりあえず全探索

実装

結果

ox- 195.58+263.97*0 1003 -> 990

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

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

あとで解く。解いた

advisoryを読んだ。

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