トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

SoundHound Inc. Programming Contest 2018

[競技プログラミング,競プロ解説]

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の場合で場合分けします。これは単にその2通りで計算が変わるからでしょう。

 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のカードを重複を許して2枚並べてその差分が1になるのは(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
お名前: コメント: