SoundHound Inc. Programming Contest 2018 - C
問題は単純なのだが、解法が全然思いつかず。
- C - Ordinary Beauty
- n, m, d が与えられるとき
- 1 <= n <= 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
解説
方針
期待値の線形性を利用して数列の美しさの算出を分解する
隣り合う 2 項は m − 1 通り存在します。
わかる（自明）。サイズmの数列を作るので、間に入るそれぞれの要素の差分はm-1個になるはず。
期待値の線形性から、m − 1 通りそれぞれについて差の絶対値が d である確率を求めて、足し上げれば答えが求まります。
は？なんで（半ギレ）よくわからないので、これを処理①と呼んでおきます。 ページ作りました 期待値の線形性。高校数学レベルなのですが自分は文系なので知らず…
図の前半は例です。各桁が独立に確率 1 / 2 で 1 か 2 であるような 9 桁の数字の並びに対して、特定の並びになる期待値を出す方法を書いてます。今回の問題はそれとだいぶ似ていて、各桁が独立にある確率でd=xであるようなM桁の数字の並びに対して、特定の並びになる期待値を出す方法を出す必要がある。
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)のとき。これを一般化したものとわかる。
解答コード
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
SoundHound Inc. Programming Contest 2018 - D
解説
方針
- hoge
ordinary_beauty.png