yukicoder contest 427 (ゲーム問題コンテスト) 概要

2024-04-12 21:20:00〜2024-04-12 23:20:00 (2h)のコンテストです。
参加登録などはありません。問題が公開されたら、回答を提出すれば大丈夫です。
誤回答によるペナルティーはありません。

# ナンバー 問題名 レベル 作問者 テスター Solved Fav
A 2721 "Don't say N" Game MasKoaTS p-adicp-adic ygussanyygussany 141 0
B 2722 Kenken Fight MasKoaTS p-adicp-adic ygussanyygussany 89 4
C 2723 Fortune-telling by Flowers MasKoaTS p-adicp-adic ygussanyygussany 71 1
D 2724 Coprime Game 1 MasKoaTS AngrySadEightAngrySadEight ygussanyygussany 68 1
E 2725 Coprime Game 2 MasKoaTS p-adicp-adic ygussanyygussany 60 5
F 2726 Rooted Tree Nim MasKoaTS nok0nok0 ygussanyygussany 54 3
G 2727 Tetrahedron Game MasKoaTS nok0nok0 ygussanyygussany 30 1

コンテスト情報

MasKoaTSによる単独writerコンテストです。問題数は全部で7問、コンテスト時間は120分です。

本コンテストは「ゲーム問題コンテスト」と題しまして、二人零和有限確定完全情報ゲームを題材とした問題のみを集めたコンテストとなっています。
詳しい情報については、下の「ゲーム問題について」の項をご覧ください。

すべての問題について、C++, PyPy3でのACを確認済みです。

実行時間制限の関係上、問題や使用する言語・処理系によっては想定解でもACできない可能性があります。
特に、Pythonを使用している方は処理系にPyPy3を選ぶことを推奨します。

皆様のご参加を心よりお待ちしております。


ゲーム問題について

本コンテストでは、二人零和有限確定完全情報ゲームを題材とした問題のみが出題されます。

「二人零和有限確定完全情報ゲーム」とは？（クリックで展開）

ゲーム理論において、次の性質をすべて満たすゲームを「二人零和有限確定完全情報ゲーム」と言います。

  • 二人：ゲームに参加するプレイヤーは二人である。

  • 零和：ゲームに参加する二人のプレイヤーの利得関数の和は常に $0$ である。

  • 有限：ゲームは必ず有限回数の手番によって終了する。

  • 確定：ゲーム中の選択はすべてプレイヤーの意思によってなされ、ランダムな要素が介入しない。

  • 完全情報：ゲーム中のすべての情報が双方のプレイヤーに公開されている。

厳密には、展開型ゲームであって、次の性質をすべて満たすものを指します。

  • 二人：ゲーム中に意思決定を行う主体の数は $2$ である。

  • 零和：ゲームに参加する二人のプレイヤーをそれぞれA, Bとし、その利得関数をそれぞれ $E_{A}, E_{B}$ とすると、$E_{A} + E_{B} = 0$ が常に成り立つ。

  • 有限：ゲーム木は有限グラフである。

  • 確定：ゲーム木に偶然手番が存在しない。

  • 完全情報：任意の情報集合 $I$ に対して唯一の手番の系列 $s$ が存在し、$I = \{ s \}$ である。

特に、各問題で行われるゲームでは、次の条件がすべて成り立ちます。

  • ゲームは必ず有限回数の手番によって終了する。

  • ゲームに参加する二人のプレイヤーをそれぞれA, Bとすると、最終的なゲームの結果は次のうちいずれか $1$ つに定まる。

    • Aの勝ち、かつBの負け

    • A, Bともに引き分け（一部の問題のみ）

    • Aの負け、かつBの勝ち

また、ゲーム中に両者が「最善を尽くす」とは、各手番において、両者が次の手順によって意思決定を行うことを意味します。

  1. 自身に必勝戦略が存在する（複数存在する場合は無作為に $1$ つ選ぶ）ならば、これに従う。

  2. 自身に必勝戦略が存在しない場合において、相手に必勝戦略が存在しない局面に遷移可能ならば、
    この局面（複数存在する場合は無作為に $1$ つ選ぶ）に遷移する選択を行う。

  3. 上記以外の場合は、無作為に意思決定を行う。