Xmas Contest 2018 D: Devilish Dice 解説

Xmas Contest 2018

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 数学センスを問う問題にしてみました．不思議な問題ですね．

Xmas Contest 2018 C: CombinatioN 解説

Xmas Contest 2018

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

問題概要

Pascal の三角形を書こうとしたが，ある場所で足し算を大きい値に間違えてしまった (→間違いがそこから伝搬)．そして一部消えてしまった．というものが与えられるので，間違えた場所を特定せよ．

部分点解法

(i, j) で間違えて x 大きい値を書いてしまったときの影響を考えると， l \ge j かつ k - l \ge i - j を満たす (k, l) のところが \binom{k - i}{l - j} x だけ大きくなることがわかります．

これを用いると，すべての (i, j) を間違えた場所の候補として，与えられた条件がすべて満たされているか調べる，という解法が得られます (増えているところの情報から x の値を求めて，複数個になったらダメ)． O(N^4) 時間になります．

解法 1

制約をよく見ると，消えずに残っている値は 10^9 以下と書いてあります．ということは，正しい値以上が書いてある場所は \binom{i}{j} \le 10^9 なところしかありません．これは N^2 よりだいぶ少なくて， N = 500 では 4600 箇所です．

大きい方にしか間違えないので，正しい値未満が書いてあったら IMPOSSIBLE です．これで弾かれなければ，部分点解法で間違えた場所 (i, j) を決め打ったあと調べる箇所が 500^2 から 4600 になるので，間に合うかもしれない気がしてきます．実際，実装の定数倍や言語次第かもしれません．

もう少し速くするには，間違えた場所の候補 (i, j) を試すとき， \binom{i}{j} > 10^9 なら間違えても情報が出てこない，ということを用います．まとめるとこんな感じ：

正しい値未満が書いてあったら IMPOSSIBLE
foreach (i, j):
  if check(i, j):
    (i, j) を答えの候補に追加
答えの候補が 0 個なら IMPOSSIBLE，1 個ならそれを出力，2 個以上なら AMBIGUOUS

function check(i, j):
  if C[i][j] > 10^9:
    正しい値より大きい値が書いてあれば return false  // これは前計算しておく
    return true
  foreach 何か書いてある (k, l):
    if k >= i and l >= j:
      x := (A[k][l] - C[k][l]) / C[k - i][l - j]
      x が正の整数でなければ return false
      x を x の候補に追加
    else:
      A[k][l] = C[k][l] でなければ return false
  x の候補が 2 個以上なら return false
  return true

これなら一番計算が重い部分が 4600^2 で，無事間に合います．

解法 2

正しい値より大きい値が書いてある場所 (k, l) をひとつ決めると，間違えた量 x は A_{k,l} - \binom{k}{l} の約数なので，それをすべて試します．正しい値より大きい値が書いてあるという情報から，間違えた場所 (i, j) がどんどん絞られていきます．というのも， \binom{i-k}{j-l} の値から i-k と j-l がほぼ決定されるからです ( 1 のときを除いて，最大 6 通りしかないようです)．

計算量のボトルネックは， 4600 \times (約数の個数) とかになります．実装は結構大変かもしれません．さらに，AMBIGUOUS 等の判定で間違えがちです：例えば，一番下の段でひとつだけ消えていて，他が全部正しいとき，正しい値しか書いていないですが間違えた場所は一意に特定されます．

コメント

適当に問題設定を考えついて，最初は約数を調べる解法を思いついて適当に投下したのですが，snuke さんがすぐに言ってきた素直に全箇所調べる解法が十分速いことに気づき，簡単めでいいかな～と思って採用されました．しかしはまりがちポイントが大量にあることが徐々に発覚し，綺麗な実装ができますかという問題に．一発で通せた方はすごい！

Xmas Contest 2018 B: Bit Smaller 解説

Xmas Contest 2018

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

問題概要

34425 = 3^4 425 とか， 189637632 = 1^{89} 6^3 76^3 2 とか，そういうののうち 20181224 以下のものをすべて求めよ．

解法 1

全探索しましょう．数の切り方は高々 64 通りしかないのでなんとかなると思います．

先頭のほうから切っていく感じで再帰で実装するのもよいと思います．

枝刈りとかがんばらない限りは実行にそれなりに時間がかかりますが (わたしのは数分でした)，答えだけ出せばいいので安心．

a_i^{b_i} たちの積を求めていくより a_i で b_i 回割っていく，みたいなののほうがオーバーフローを気にせずに済んで枝も刈れていろいろお得かも (ただし a_i = 1 に注意)．

解法 2

https://oeis.org/A096298

親切にもふたつめの答えまで書いてあるので OEIS で検索すると見つかります．が，

  • "not ending with 0" と書いてあるように，条件を満たす数の末尾に 0 をつけてもやはり条件を満たす
  • 切り分けたときに 0 が入っていたり 0 で始まっていたりそういうのも含まれている

ことに注意してください．

コメント

面白算数 (?) ネタを見つけたので易しめの問題にしてみました．作問陣は OEIS で検索するのをすっかりさぼっていたのですが，微妙に条件が違って逆にトラップになってたようで面白いですね．

この問題の範囲では一の位が 5 (か 0) の解しかないですが，他がないわけではないです (問題概要のとこの例とか)．

2592 = 2^5 9^2 みたいに最後の部分がないパターンも綺麗ですが，探索で見つかる範囲だと全然ないようです．桁を増やせば，例えば 193069772981724883114815346493095941104647648408310082599392948515311247361 とかがあります (見た目がやばいですがこうやって構成されています： https://math.stackexchange.com/a/2126667)．