SoundHound Inc. Programming Contest 2018 -Masters Tournament- C問題 「Ordinary Beauty」
問題リンク :
https://beta.atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_c
問題文を読んだ前提で解説を書いていきます。
この問題では色々言われていますが、これに限らずこの手の問題では特定のケースに対して手元でどうなるかを書いて試し、それの一般化(文字式に置くこと)を試みることが重要です。実際にコンテスト中ぼくが試したケースも交えて実験をしてみましょう。
①N=3、M=2、D=1のとき
手書きですいません。まず1~3を2列並べてみました。それぞれの数が選ばれる確率は等しそうなので(等しいです)それぞれの1,2,3が選ばれる確率はそれぞれ1/3ですね。それを２つなので特定の数の組（(1,2),(2,3)など）が選ばれる確率はそれぞれ1/9になります。ではここで「美しさが増加する数字の組とその確率」を考えます。
先程の図に線を書き加えました。ここで黄色で線を書いた組に関しては赤の数と青の数の差が１(D)である、すなわち美しさが増加する組を指しています。灰色で線を書いた組はそうでない組を指しています。このケースでは増加する組が4組、増加しない組が5組で、美しさが増加する確率は4/9だということがわかります。今回のケースではM=2のためこのまま4/9が答えになります。ここまでよろしいでしょうか？
②N=4,M=2,D=1のとき
最初から線を書き込んじゃいました。このときも先程と同様に考えると黄色が6組、灰色が10組で増加する確率＝答えは6/16だということがわかりました。簡単のため、約分はしないままでいきます。
③N=4,M=2,D=2のとき
Dの値を変化させました。そうすると答えが6/16から4/16になってしまいました。なぜでしょうか。ここで「1~Nの中で複数の美しさが増加する組に入っている数」の条件を考えます。
①のケースの時、美しさが増加する組は(1,2),(2,1),(2,3),(3,2)でした。左の数だけ注目すると2が二回登場することがわかりますか？同様に②のケースでは2と3が二回登場し、③では全て一回です。
考察を省略して結論を言うと、左の数がkの時右の数はk+Dもしくはk-Dである場合に組みが成立します。ので右の数(k+Dとk-D)が1~Nの範囲にないと組が成立しないんです。
このことを考えると左の数がkの時、登場が一回か二回かを次の条件で定めることができます。
kが1~Dのとき 登場は一回
kがD+1~N-Dのとき 登場は二回
kがN-D+1~Nのとき 登場は一回
よって、1*D + 2*(N-2D) + 1*D = 2N-2D =2 (N-D)回が登場回数であることがわかります。全ての組み合わせの数は左の数がN通りで右の数がN通りの合計N^2通りなので「美しさが増加する確率」は2(N-D)/N^2であることがわかりました。まだまだ終わりではありませんよ？次のケースを考えなくちゃいけません。
③N=3,M=3,D=1のとき
数が３列になっちゃいました。ここがこの問題の最も難解な部分だと思います。ですがこう考えてみてください。
１列目と２列目において美しさが増加する確率は4/9です(これはさっきやりました)。２列目と３列目を見てください。全く同じ形をしているでしょう？実は２列目と３列目においても増加する確率は4/9なんです。ここはしっかり考えてみてくださいね。
数列全体で見て増加を２回する確率は(4/9)^2で16/81で、１回増加する確率は2*4/9 * 5/9で40/81です。全く増加しない確率は(5/9)^2で25/81ですね。
よって期待値は2*(16/81)+1*(40/81)+0*(25+81)=72/81=8/9になります。あれ？これは4/9の2倍ではないか？
そうです。ここの数は4/9の増加を2回(M-1回)やったので8/9になるんです。これがいわゆる「期待値の線形性」にあたります。実際はこれと同じことをM-1回繰り返すので求める答えはさっきの2(N-D)/N^2に(M-1)を掛けて2(N-D)(M-1)/N^2になります。さっきはM=2だったのでM-1=1となって見えなかったんですね。これを計算して提出すればAC…ちょっと待った！まだコーナーケースがあります！
④N=3 M=3 D=0のとき(灰色の線は省略しました)
なんと！2(N-D)(M-1)/N^2じゃなくて(N-D)(M-1)/N^2になってるではありませんか！
これの理由なんですが先程「左の数がkの時右の数はk+Dもしくはk-Dである場合に組みが成立する」と言いました。D=0の時k+Dとk-Dは等しくなってしまいます！なので登場する回数は必ず一回となってしまいます！なのでD=0の場合だけif文で分けて(N-D)(M-1)/N^2としてやる必要があるんです。長文に御付き合いくださりありがとうございました。これにてACです。
おわりに
計算の方法・順番によっては誤差が生じる可能性があります。十分気をつけましょう。
あわせて解きたい
ABC008-C コイン
