「 今週のお題：番号の対応表で作るグループ」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 入力 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 となる状況」とグループ数は同じになります。
そのため、グループ数の期待値は$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} $$ ということで、目的の漸化式が出てきました。
終わりに
上のように式が綺麗に導き出せれば簡単ですが、気付けないとどう解いていいか分からないところですね。
