AOJ 2557 : Iyasugigappa
Iyasugigappa | Aizu Online Judge
問題概要
asi1024様が問題文の完全日本語訳をしてくれています。
- よくありそうなゲームの問題ですが、重要なのは以下の部分。
- カエルとイタチは自分の得点を最大化する。
- カッパのみカエルの得点を最小化する。
- カエルとイタチは全員が自分の得点を最大化する行動を取ると仮定して行動する。
- カッパはカエルとイタチが上の仮定のもと動くと分かっている。
解法
- 各プレイヤーの思考に反射（？）が起きているので普通に
- カエル：カエルの得点最大化
- カッパ：カエルの得点最小化
- イタチ：イタチの得点最大化
- するようにメモ化再帰するとよくない
- 言葉では分かりづらいので絵で描くと以下のような遷移をする。
-
返す値として『河童視点での各プレイヤーの得点』と『蛙鼬視点での各プレイヤーの得点』の両方を持つ。
-
蛙鼬の行動は、青点線の遷移が一番良い遷移を選ぶ。
- 河童の行動は、赤実戦と青点線で独立して良い方を選ぶ。
- とすると、問題文のプレイヤーの思考に沿ったシミュレーションができる。
- 最終的な答えは赤実線（河童視点）の各プレイヤーの得点になる。
- あと注意すべき点として
もし、複数の選択肢がある場合
"ターンの終了時のプレイヤーの保持するアクションカードの値の合計値を最大化する"ような行動をとる。 - ターンの終了時なのでそのターンに消費するアクションカードの値の中で一番小さいものを選べばよい。(使わないが一番いい）
- これで行動が一意に定まる。
ソースコード
感想
各プレイヤーの思考が異なる系ゲーム問題をはじめて解いたので解き方の知見になった。
あとハマった点、アクションカードの効果を
y[i] 番目のカードを削除する
だとずっと思っていてバグっていた。
正解は
y[i] 番目のカードをギロチンの直前に移動する（そのカードを自分の得点にしてターンを終える）
