hogloidのブログスマートフォン用の表示で見るhogloidのブログへなちょここの広告は、90日以上更新していないブログに表示しています。Dice最近は公式解説があるから解説記事なんて滅多に書かないんですが、まさかの想定解が全探索の問題に対して綺麗なパターンを見出してしまったので、解法をメモしておきます。writer,testerは全員全探索して埋め込みです。(じゃっぷるさんは全探索を0.1s/1ケースくらいまで高速化しててプロだった)むしろこっちが解説を聞きたい。あなたは嘘つきですかと聞かれたら「YES」と答えるブログ(以下、ネタバレ防止の空行)初見で、こんなのKが偶数なら1/2で、終わり!と思ったものの、さすがに順位表から怪しい雰囲気を感じ取り、なんとか半分より勝てないか考えてみる。ようは、ジャンケンのようにNすくみの関係を作れるとうれしい。3333372は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以下で自由に決めてよい。勝てる確率と、1番目のサイコロの小の数を決めたとき、2->1の勝率は、2番目の小の数について単調減少2番目の小の数を増やすと、3->2の勝率は増えるので、決めた勝率を満たせる範囲でなるべく多く小を入れる。1が決めた確率を満たすならOK、そうでなければ失敗。勝率は二分探索してもいいし、制約が小さいので全探索してもよい。後日、↑のツイートを見て証明を試みたが、失敗。サイコロiに書いてある値がa,b,...だったとき、i+1に書く数はε,a+ε,b+ε,...だけ考えればいいのだが、サイコロについて、大と小の2種の値だけでよい、ということがどうしても示せず。i+1で3/4ぐらい勝てるのに対し、a種類で均等ならa*(a+1)/(2*a^2)と、勝てる確率が減ることを考えると、わざわざ色んな数を使わなくても...という気がする。誰か分かったら教えてください。R3解いたものリスト月別アーカイブはてなブログをはじめよう!hogloidさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。