Xmas Contest 2018 D: Devilish Dice 解説

https://atcoder.jp/contests/xmascon18/tasks/xmascon18_d

問題概要

$N$ 個の $K$ 面さいころの目を上手く決めて，「どのさいころについても，他のあるさいころを選ぶと確率 $p$ 以上でそれより大きい目が出せる」となる $p$ を最大化せよ．

考察

くろうさ「先にさいころ選んでいいよ」

しろうさ「やさしい」

くろうさがやさしいわけはなく (?)， $N \ge 3$ かつ $K \ge 3$ ではこれはくろうさ有利なゲームです．例えば， $X_1 = (1, 7, 8),\, X_2 = (2, 3, 9),\, X_3 = (4, 5, 6)$ という $3$ 個のさいころを考えると， $\Pr[ X_1 \lt X_2 ] = \frac{5}{9},\, \Pr[ X_2 \lt X_3 ] = \frac{6}{9},\, \Pr[ X_3 \lt X_1 ] = \frac{6}{9}$ となり，三竦みの関係が生じます．他にも大量の例が https://en.wikipedia.org/wiki/Nontransitive_dice に載っています．

とても手に負えなさそうですが，問題を単純化できる考察がいくつかあります．まず，別のさいころに同じ値を書く意味はありません．同じ値があるとき片方を少し増やしてもくろうさは何も損しないからです (くろうさの勝率 $\min\{ \max\{\ldots\}, \ldots, \max\{\ldots\} \}$ の中身が増えるだけなので)．

また，「 $n$ 竦み」のような関係のみ考えればよいです．あるさいころに対して，それに強いさいころ，さらにそれに強いさいころ，……というようにとっていくとサイクルができるので， $n \le N$ に対する，「 $\Pr[ X_1 \lt X_2 ] \ge p,\, \ldots, \Pr[ X_{n-1} \lt X_n ] \ge p,\, \Pr[ X_n \lt X_1 ] \ge p$ となる最大の $p$ 」で答えが上から抑えられます．逆にこういうサイクルをひとつ作ってしまえばあとは弱いさいころを好きなだけ足せばよいです．

解法 1

ここまでを念頭にマシンパワーで DP をします． $K$ を固定します．

さいころ $X_1, X_2, \ldots$ の順で目を決めていくことにすると， $X_{i+1}$ を決めるときには $X_1$ と $X_i$ 以外の情報は要りません．ということで， $X_1$ と $X_i$ の目の大小関係を状態 ( $\binom{2K}{K}$ 通り) として， $\min\{ \Pr[ X_1 \lt X_2 ], \dots, \Pr[ X_{i-1} \lt X_i ] \}$ を最大化する DP をします．

DP の遷移をするには， $X_1$ と $X_i$ の大小関係それぞれに対する， $X_1$ と $X_i$ と $X_{i+1}$ の大小関係 ( $\binom{3K}{K}$ 通り) が一見要りそうですが， $X_1$ と $X_{i+1}$ の大小関係を決めてしまえば十分で，なぜならその制約の下では $X_{i+1}$ を $X_i$ に対してできるだけ強くしてしまってよいためです．

DP テーブルをどの $n$ まで作るかですが，やってみるとそのうち変わらなくなるので打ち切れます ( $K \le 10$ なら実は $n = 6$ までしか要りません)．あるいは後述のように $K$ に対する勝率の上限を求めておいてそれを達成したら打ち切る，というのもできます．

こんな感じで， $\binom{2K}{K}^2$ に多項式がかかったような計算量で解けるので，がんばって回して答えを埋め込みましょう．細かい定数倍高速化としては，例えば「 $X_1$ が目の最大値を持つことにしてよい」を採用すると $4$ 倍速くなって嬉しいです．わたしのコードは実行時間 $6$ 分くらいでした．

japlj さんと snuke さんは，ちょっと別のアプローチのマシンパワー探索解法をしていました．答えを決め打って必要な $N$ を求めにいく方針で，枝刈りが上手く効くようです．

解法 2

いろいろ実験をすると，「 $i$ 番目のさいころには $i$ と $i+N$ しか書かない」というパターンで結構いい感じの勝率が得られていそうなことに気づけるかもしれません (後述のように，これはただの偶然でも突拍子もない発想でもないです)．実際に $K \le 10$ ではこれですべて正解できるようです．

コンテスト中の hogloid さん，終了直後の omeometo さんの解法がこのパターンを見つけた方針でした．コンテスト前には，snuke さん作のゲームを手で遊んだ結果から似たようなパターンを試していたのですが，変な greedy をしていて $(N, K) = (4, 7), (5, 8)$ で不正解になっていたので，全探索系以外は厳しいかも？と思っていたのでした．

このパターンを仮定するなら，いろいろな解法が考えられます．例えば，「 $1$ 番目のさいころの $1$ の個数」と「 $i$ 番目のさいころの $i$ の個数」を状態として持つ DP ( $O(K^3 N)$ 時間) が楽だと思います．

さて，この仮定が正しいかというと，実は反例があるようです． $(N, K) = (3, 27)$ で，

144444444444444444444444444
222222222225555555555555555
033333333333333336666666666

というさいころを考えると，くろうさの勝率は $\frac{443}{27^2}$ ですが， $2$ 値さいころだけではこれは実現できません．ただ，この反例のように，「 $1 \le i \le N - 1$ に対しては $i$ 番目のさいころには $i$ と $i+N$ しか書かない， $N$ 番目のさいころには $0$ と $N$ と $2N$ しか書かない」というパターンなら正しいのではないかと予想しています．証明を募集しています！！

参考 1 (fixed K)

$K$ を固定したときの勝率の最大値は $1 - \displaystyle\frac{\left\lfloor \frac{K+1}{2} \right\rfloor \left\lfloor \frac{K+2}{2} \right\rfloor}{K^2}$ です．

これは，「中央値が最小」みたいなさいころを考えることで上から抑えられます．正確には， $n$ 竦みの中で自身の $t$ 番目の値が最小のさいころを考えると，それは他のさいころに高々 $1 - \frac{t (K+1-t)}{K^2}$ でしか勝てないので， $t = \left\lfloor \frac{K+1}{2} \right\rfloor$ ととることで示せます．この評価の仕方は， $2$ 値さいころだけを考えてもかなり上手くいくことを示唆しているかもしれません．

最大値をとる具体的な構成もできて，例えば $K = N$ として，「 $i$ 番目のさいころには $i$ が $i$ 個で残りは $i + N$ 」というようにすればよいです ( $N$ はもっと小さくとれます)．

$K \to \infty$ とするとこの値は $\frac{3}{4}$ になります．さいころに限らない一般の確率分布を考えても，勝率は $\frac{3}{4}$ が上限ということですね．

参考 2 (fixed N)

$N$ を固定したときの勝率の上限は $1 - \displaystyle\frac{1}{4 \cos^2\left( \frac{\pi}{N+2} \right)}$ です (!?)． $N = 1, 2, 3, 4$ ではそれぞれ $0, \frac{1}{2}, \frac{-1+\sqrt{5}}{2}, \frac{2}{3}$ となります．

詳しくは https://mathoverflow.net/a/119885 をご覧ください．

わたしは証明をちゃんと把握できていないのですが， $2$ 値の確率分布だけを考えればよいことを示すという方針のようです． $K$ が固定されているときに同じ議論は適用できないのですが， $2$ 値さいころだけを考える有力な根拠となります．解法 $2$ の最後で述べた予想も， $N$ を固定したときの最適解を近似したものがベストだろう，という考えに基づいています．

三竦みが作れるってだけでも面白いのにいろいろ楽しい数学が奥に潜んでいる，という感じの話題を，全部有限にして探索力 and/or 数学センスを問う問題にしてみました．不思議な問題ですね．