同時接続数:107

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	74	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$ つ選ぶ）ならば、これに従う。

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

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