(o_o)

ブログ。

AOJ2557 Iyasugigappa

問題概要
カエルとカッパとイタチがカードゲームをしている

このゲームでは,ギロチンカード1枚,貴族カード12枚,アクションカード6枚を使う.貴族カードとアクションカードの表には,それぞれ整数値が書かれている.まず,ゲームを始める前に,プレイヤーはテーブル上に一列に12枚の貴族カードを伏せて,その右にギロチンカードを置き,それぞれのプレイヤーには2枚のアクションカードが配られる.この問題では,全てのカードをオープンにして,完全情報ゲームにするものとする.

ゲーム中,カエル,カッパ.イタチの順にターンが回ってくる.ターンはアクションフェーズと処刑フェーズに分かれており,その順に行われる.

アクションフェーズでは,持っているアクションカードを1枚使うことができる(使わなくてもよい).値yが書かれたアクションカードを使うとき,ギロチンカードの前の貴族カードから数えてy番目(1-based)の貴族カードをギロチンカードの直前に移動する.このとき,少なくともy枚の貴族カードが場になければならない.もし場の貴族カードがy枚以下なら,アクションカードの効果は無効になる.使ったアクションカードは手札から取り除かれる.

処刑フェーズでは,ギロチンの直前にある貴族カードが取り除かれ,プレイヤーはその貴族カードに書かれている値の勝利点を得る.

ゲームの終了条件は全ての貴族カードが場からなくなることである.

それぞれのプレイヤーは以下の戦略に従って行動する.
・それぞれのプレイヤーは自分の最終的なスコアが最大化されるような戦略に従って行動すると仮定される.
・カエルとイタチは実際にその戦略に従った行動をする.
・しかし,カッパはカエルの最終的なスコアが最小化されるように行動する.
・カエルとイタチは,カッパも自分の最終的なスコアが最大化されるように行動していると思っているし,カッパもそのことを知っている.
・適した行動が複数存在する場合,そのターン終了後の自分のアクションカードの合計値が多くなるように動く.

それぞれのプレイヤーの最終的なスコアを求めよ

解法
カエルとイタチ,カッパについての再帰関数を書く.メモ化は必要ない.再帰関数の返り値は (最善を想定したときの最終的な結果, 次の1手) としておく,カエルとイタチの関数については容易に書ける.カッパの関数については,カエルとイタチの関数を使ってシミュレーションさせる感じの再帰関数にする. 結構頭がこんがらがってややこしい.



gist57ab6ba1f37e714f0c21