hotpepsiの練習帳

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