hogloidのブログ

へなちょこ

Xmas Contest 2018 D: Devilish Dice

概要:
D - Devilish Dice

最近は公式解説があるから解説記事なんて滅多に書かないんですが、まさかの想定解が全探索の問題に対して綺麗なパターンを見出してしまったので、解法をメモしておきます。

snukeの解法はこちら:
Xmas Contest 2018 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

(以下、ネタバレ防止の空行)




























初見で、こんなのKが偶数なら1/2で、終わり！と思ったものの、さすがに順位表から怪しい雰囲気を感じ取り、なんとか半分より勝てないか考えてみる。
ようは、ジャンケンのようにNすくみの関係を作れるとうれしい。
15分ぐらいで、以下のような配置を思いついた:
Dice 1: 155555
Dice 2: 222666
Dice 3: 333337
2は1に、3は2に21/36の確率で、1は3に25/36の確率で勝てる。これを一般化し、

  • サイコロiの目にはiとM+iのみ書き(Mは十分大きい定数)
  • iの増加とともに書かれる小さい数を増やしていく

ことで、N>2なら半分より高い確率で勝てそう！
iを小、i+Mを大と呼ぶことにすると、i+1はiに小v.s.大でしか負けないので、小の増加を無視するなら3/4ぐらい勝てる。N番目と1番目の勝負で小v.s.大の起こる組み合わせを半分以上にしておけば、そこでもやっぱり勝てる。

とりあえず、このパターンのみ考えコンテスト中は実装した。
Nが多くて困ることはない (クソザコサイコロをダミーで作ればよいだけ) ので、サイコロの個数はN以下で自由に決めてよい。
勝てる確率と、1番目のサイコロの小の数を決めたとき、

  • 2->1の勝率は、2番目の小の数について単調減少
  • 2番目の小の数を増やすと、3->2の勝率は増える

ので、決めた勝率を満たせる範囲でなるべく多く小を入れる。これを繰り返し、N vs. 1が決めた確率を満たすならOK、そうでなければ失敗。
勝率は二分探索してもいいし、制約が小さいので全探索してもよい。


後日、↑のツイートを見て証明を試みたが、失敗。
サイコロiに書いてある値がa,b,...だったとき、i+1に書く数はε,a+ε,b+ε,...だけ考えればいいのだが、サイコロについて、大と小の2種の値だけでよい、ということがどうしても示せず。
直感的には、2種類で大小均等ならi v.s. i+1で3/4ぐらい勝てるのに対し、a種類で均等ならa*(a+1)/(2*a^2)と、勝てる確率が減ることを考えると、わざわざ色んな数を使わなくても…という気がする。誰か分かったら教えてください。