「 今週のお題：オリンピックの開催地はどうやって決まる？」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 入力$n$に対し、$n$個の候補地から「繰り返し最下位消去ルール」という投票方法で1個を選ぶ時、その投票パターンが何通りあるかを調べる。※ただし、候補地や得票数そのものの区別はしない
- 「繰り返し最下位消去ルール」とは次のような方法である。
ちょっと条件がややこしいですが、例を挙げると、
- 1回目の投票: 1位 5票、2位 3票、同数3位(3候補地) 1票 → 過半数なく、複数最下位のため最下位決定を行う
- 2回目の投票(最下位決定): 1位: 6票、2位 3票、3位 2票 → 1位が過半数で最下位に決定、次の投票から除外
- 3回目の投票: 1位 5票、2位 3票、3位 2票、4位 1票 → 4位が最下位のため除外
- 4回目の投票: 1位 6票、2位 3票、3位 2票 → 過半数で1位の候補地が選出
この場合の投票パターンは、
- 1回目過半数未達、最下位3候補 → 2回目過半数で最下位決定 → 3回目最下位除外 → 4回目過半数でトップ選出
ということになります。
解説
提出したのは、次のRuby(39)でした。
x=s=1
3.upto(eval *$<){s+=x+=1+x*s}
p x
まず、件のパターン数を$x_n$とします。
そうすると、$n=2$であれば、必ずどちらかが過半数になる ( 同数は考えない ) ため、すぐ決着します。すなわち
- $x_2=1$
次に $n\ge 3$の場合です。トップ過半数の1パターンに加え、最下位を除外するパターンがあります。ここで、最下位はトップ以外、最大で$n-1$候補地までありうるため、
- $x_n=1+\sum_{k=1}^{n-1} (最下位がk候補地になる場合のパターン数)$
ということです。ただ、いずれの場合も最下位決定後は$n-1$候補に減って再投票なので、
- $x_n=1+x_{n-1}\sum_{k=1}^{n-1} (同数最下位のk候補地から最下位を選出するパターン数)$
ところが、この () の中身とは、「繰り返し再開消去ルール」のパターン数そのものなので、$k=1$の場合の1通りを別にすると、
- $x_n=1+x_{n-1}(1+\sum_{k=2}^{n-1} x_k)$
と漸化式がまとめられます。この$\sum$の部分を$S$とすると、
- $x_2=S_2=1$
- $x_n=1+x_{n-1}(1+S_{n-1})$
- $S_n=S_{n-1}+x_n$
そこで、この漸化式を $n=3$ から目的の$n$まで回すことで、答えが得られます。
終わりに
最下位を決定する際に、トップ選出と同じ方法を使うというのが面白いところですね。
