Hatena::Grouptopcoder

hotpepsiの練習帳

2015-01-01

SRM 637

00:55

Div1 Easy (250) GreaterGame

問題

  • 1から2×Nまでの数が書かれた2×N枚のカードがある
  • 2人のプレーヤーにそれぞれN枚のカードを配る
  • それぞれのプレーヤーの手札の配列が与えられる
  • 相手は順番に出す手札と、順番が決まっていない手札がある
  • 出した数値が大きいほうが1点得る
  • 一人目のプレーヤーの点数の期待値を求める

方針

  • 相手の手のうち、確定しているものについて、小さい順に処理する
  • 勝てるものには最小限で勝てるものを、負けるものには手持ちの最小値をぶつける
  • 不明な部分については、出さなかったカードについて単純な期待値を求める
  • Failed System Test
  • 負けるものの処理が抜けてた
  • https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_637/GreaterGame.cpp

Div1 Medium (500) PathGame

問題

  • 縦2マスの通路がある
  • 升目は白か黒で、白い升目だけ通れる
  • 2人で交互に升目を黒く塗る
  • ただし左端から右端まで通れる状態を維持する必要がある
  • 塗れないほうが負け
  • 最善手のときの勝者を求める

方針

  • Grundy数でも解ける
  • cafelierさんのを写経
  • 塗れるブロック毎に分割して、それぞれのGrundy数を求める
  • 塗り状態は、両方白、上だけ黒、下だけ黒のいずれか
  • 連続する両方白の部分がひとつのブロック
  • それぞれのブロックについて、左端の塗り状態L + 長さNの白い部分 + 右端の状態R、のGrundy数を求める。Nの全範囲について、塗れる部分のGrundy数の集合を求める
  • N=1のGrundy数は、両方の上か両方の下が空いているときは1、それ以外は0
  • 塗れる部分が分割されるときは、それぞれの部分のGrundy数のXORを取る
  • https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_637/PathGame.cpp

結果

x-- 0pts 486th/688 rating 1564 -> 1467 (-97)

GCJ 2014予選Dの問題に似ている。実装中に方針が適当になってしまった。

http://togetter.com/li/735960

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20150101