読者です 読者をやめる 読者になる 読者になる

「 今週のお題:番号の対応表で作るグループ」問題解答 ( CodeIQ )

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 入力 n ( $n\le 6$ ) に対し、次のように定めるグループ数の期待値が n を超える、最小の人数 ( m ) を出力する
  • グループは次のように定める
    • m人の参加者全員に、予め 1~m の申し込み番号が付与されている
    • 参加者の到着順 ( ランダム ) に、1~m の座席番号を付与する
    • ある人Aの申し込み番号と、ある人Bの座席番号が一致するとき、A,Bは同一グループとする
    • 上記「同一グループ」の関係を辿れる人全員が同一グループ、辿れない人は別グループとなる
    • 申し込み番号と座席番号が一致する人は、その人1人のみのグループとなる

例えば、次のように座席番号が割り振られた場合、申し込み番号1,2,4と5,6がそれぞれ同一グループ、3は単独のグループで、全部で3グループということになります。

申し込み番号 座席番号
1 4
2 1
3 3
4 2
5 6
6 5

解説

ざっくりとした解説

実際に、人数$m$に対するグループ数の期待値$E(m)$を考えてみます。問題文から$E(3)=1.833\cdots$というのが分かっていますから、

$m$ $E(m)$
$1$ $1$
$2$ $1.5$
$3$ $1.833\cdots$

$m\le 3$ の状況は、上の表の通りです。…これを見てティン! と来るものがないでしょうか?
実は、$E(m)=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{m}$ という調和級数の和になっていると推測できるのですね。

なので、プログラムとしては、この調和級数の和を計算して行って、目的の n を超えるところを探すように組めば良いことになります。

提出したのは、次のRuby(41)でした。

p (1..3**n=gets.to_i).find{|i|0>n-=1.0/i}

この調和級数の和は、大体$ln(m)$と近似できますので、探索範囲の上限を$3^n$としています。

golf解

ところで…。問題の制約として$n\le 6$というのがありますから、答えを手元で計算してハードコーディングしても、ACするだけならできます。かつ、ケースは$n=1,2,3,4,6$の場合しかありませんでしたので、文字数を縮めるなら、こういうのでも良かったりします。これはRuby(29)です。

p 105379162%(46*gets.to_i-41)

補足

さて。上では「調和級数の和になっていると推測できる」とだけ言って、その検証をしていませんでした。ので補足します。

目標は$E(m)=E(m-1)+\frac{1}{m}$です。これを、申し込み番号最後 ( m ) の人の座席番号によって場合分けして考えます。

  • 申し込み番号 m の人の座席番号が m の場合
    mの人の1グループ以外は、$m-1$人でのグループ状況と完全に対応しますから、グループ数の期待値は$E(m-1)+1$となります
  • 申し込み番号 m の人の座席番号が a (≠m ) の場合
    座席番号が m となる人の申し込み番号を b ( a=bでも良い ) とすると、次の図のように、「m-1人で、申し込み番号 b の人の座席番号が a となる状況」とグループ数は同じになります。
    f:id:ange1:20160816200810p:plain
    そのため、グループ数の期待値は$E(m-1)$となります。

上記2通りの状況で、前者は確率$\frac{1}{m}$、後者は確率$\frac{1}{m}$が$m-1$通り、なのでトータルの期待値としては、 $$ E(m)=\frac{1}{m}(E(m-1)+1)+\frac{1}{m}E(m-1)\times(m-1)=E(m-1)+\frac{1}{m} $$ ということで、目的の漸化式が出てきました。

終わりに

上のように式が綺麗に導き出せれば簡単ですが、気付けないとどう解いていいか分からないところですね。