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-adic ygussany | 166 | 0 | |
B | 2722 | Kenken Fight | MasKoaTS | p-adic ygussany | 95 | 4 | |
C | 2723 | Fortune-telling by Flowers | MasKoaTS | p-adic ygussany | 77 | 1 | |
D | 2724 | Coprime Game 1 | MasKoaTS | AngrySadEight ygussany | 73 | 1 | |
E | 2725 | Coprime Game 2 | MasKoaTS | p-adic ygussany | 63 | 6 | |
F | 2726 | Rooted Tree Nim | MasKoaTS | nok0 ygussany | 58 | 3 | |
G | 2727 | Tetrahedron Game | MasKoaTS | nok0 ygussany | 32 | 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$ つ選ぶ)に遷移する選択を行う。上記以外の場合は、無作為に意思決定を行う。