SoundHound Inc. Programming Contest 2018 - (Ordinary Beauty) 再考
問題は単純なのだが、解法が全然思いつかず。
問題
- N, M, D が与えられるとき
- 1 ～ N までの種類の整数を使って
- サイズMの数列を作ったとき
- それぞれの隣り合う要素の差がDになるものの合計値を数列の美しさとして定義する
各要素が 1 以上N以下の整数である長さMの数列は全部でN^M通り存在します。 このN^M通りの数列すべてに対して美しさを求めて、それらの平均を出力してください。
n, m, d = 2, 3, 1 のとき、並べ替えのパターンと数列の美しさは
111 = 0 112 = 1 121 = 2 122 = 1 211 = 1 212 = 2 221 = 1 222 = 0
考えたこと
- 数列 [ 1, 2, 3 ... n ] から重複を許して m 個選んで並び替えたときの要素m-1個すべて差分を数え上げれば答えが出るな！（死）
- 上記は考えたのだけど、問題の制約からnもmも10^9まで行くので間違いなく制限時間に間に合わない→解法が思いつかず寝る
方針
以下、解説のリーディング
期待値の線形性を利用して数列の美しさの算出を分解する
隣り合う 2 項は m − 1 通り存在します。
わかる（自明）。サイズmの数列を作るので、間に入るそれぞれの要素の差分はm-1個になるはず。
期待値の線形性から、m − 1 通りそれぞれについて差の絶対値が d である確率を求めて、足し上げれば答えが求まります。
は？なんで（半ギレ）要は数列考える際に、m 個選んで並び替えするということは必要なく隣り合う２つの要素の差を考えてm-1個足し上げると答えになるようです。めちゃくちゃ不思議。期待値の線形性については 和の期待値は期待値の和 | 高校数学の美しい物語 が参考になりました。
リンク先の「期待値の線形性の応用例2」が、そのまま今回の問題に適用できるので解説の画像を作りました。
例
問題
d = 0の場合と d != 0の場合で場合分けする
確率を求める処理を、d = 0の場合と d != 0の場合で場合分けします。これは単にその２通りで計算が変わるからでしょう。
1 から n までの整数のペア (a, b) の差の絶対値が d である確率を求めます。
d = 0 であるとき、条件を満たすペアは (1, 1), . . . ,(n, n) の n 個です。よって、確率は n / n^2 = 1 / n です。
与えられた数1~nまでを使用して同じものを並べるだけなのでn通りあるはず。全体はn^2通りあるので、d = 0の場合の確率は 1 / n。
d != 0 であるとき、条件を満たすペアは
(1, d + 1), . . . ,(n − d, n) と
(d + 1, 1), . . . ,(n, n − d) の
2(n − d) 個です。よって、確率は 2(n−d) / n^2 です。
これも考えてみれば簡単で、1~2のカードを重複を許して２枚並べてその差分が１になるのは(1,2)のときと(2,1)のとき。これを一般化したものとわかる。
解答コード
コード自体は短く、小数点以下の桁数を0埋めしていると正解になった。
lines = $stdin.read array = lines.split("\n") N,M,D = array[0].split(" ").map(&:to_i) ans = if D.zero? 1.quo(N) else (2*(N - D)).quo(N**2) end puts "%.10f" % ((M-1)*ans).to_f
Submission #2816342 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-
