競プロ解法メモ

自分用のメモが主目的なので厳密性は求めないでください

yukicoder No.1151 チャレンジゲーム

yukicoder

問題：No.1151 チャレンジゲーム - yukicoder

Nが小さいので、全状態を列挙してDPする。状態の変数としては、（先手が取ったカード）、（後手が取ったカード）、（どちらの番か）の3変数ですべての状況を表現できる。これで、勝つ確率を求める関数P(3変数)でも作って、確率の高い遷移先を選んでいくというのが基本だと思うが、

今回はそれができない

なぜなら

「2回」の遷移後に元に戻ることがあるから

今、先手の番だとして図にしたのが次の画像

f:id:mkawa2:20210610230728j:plain

S：先手が取ったカード、T：後手が取ったカード（両方ともbit表現）

$S_{i}$ っていうのは、 $S$ の状態から $A_{i}$ のカードを追加した状態。 $T_{j}$ とか $T_{k}$ も同様。

このように2手先でループしているので、ここまでをまとめて考えないと先手がどのカードを狙うのが最適かは分からない。よって、関数Pを次のように定義する。

$P\left( S,T\right)$ ：先手の番において、先手の取ったカードがS、後手の取ったカードがTのとき、先手が勝つ確率

求めたいのは $P(0,0)$ 。

ここからは上の図を利用して、 $P$ ( $=P(S,T)$ のこと)を求める式を考える。方針としては、 $P$ =( $P$ を含む式)という等式を作り、これを $P$ について解く。

先手が狙うカードを $A_{i}$ に決め打ちしたとき、 $P$ は次の式で表される。

$P=\dfrac{1}{A_{i}}P_{1}+\dfrac{A_{i}-1}{A_{i}}P_{2}$ 　　　・・・★

先手はこれが最大になるように $A_{i}$ を選ぶことになる。次に $P_{1}$ を考える。 $P_{1}$ はループとは関係のない値なので、 $A_{i}$ を固定してしまえば定数として求めることができる。後手が $A_{j}$ を狙うとすると

$P_{1}=\dfrac{1}{A_{j}}P(S_{i},T_{j})+\dfrac{A_{j}-1}{A_{j}}P(S_{i},T)$

となる。ここで重要なのは、 $A_{j}$ を選ぶのは後手なので

$P_{1}$ が最小となるような $A_{j}$ を選ぶ

こと。これで $P_{1}$ の値は求まるので、これ以降は定数として扱う。次に $P_{2}$ について考える。後手が $A_{k}$ を狙うとすると

$P_{2}=\dfrac{1}{A_{k}}P(S,T_{k})+\dfrac{A_{k}-1}{A_{k}}P$

となる。この式を式★に代入し、 $P$ について解くと

$P=\dfrac{A_{k}P_{1}+(A_{i}-1)P(S,T_{k})}{A_{i}+A_{k}-1}$

となる。これで $P$ を求めるための準備ができた。 $i$ と $k$ を2重ループで全探索する。その際、

$i$ は $P$ が最大となるように

$k$ は $P$ が最小となるように

決めるようにする。もう少し詳しく言うと

$i$ を固定する→ $k$ を全探索して上の式より $P$ の最小値を求める →各 $i$ について求めた最小値のうち最大のものを最終的な $P$ とする

という流れになる。すべて取られた状態から、取られた枚数の降順にdpしていけばいい。初期値は、すべてのカードが取られたときで、先手の得点の方が多ければ $P(S,T)=1$ 、そうでなければ $P(S,T)=0$ となる。

提出コード：

#665321 (PyPy3) No.1151 チャレンジゲーム - yukicoder