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

「 今週のお題:オリンピックの開催地はどうやって決まる?」問題解答 ( CodeIQ )

はじめに

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

codeiq.jp

問題

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

  • 入力$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$まで回すことで、答えが得られます。

終わりに

最下位を決定する際に、トップ選出と同じ方法を使うというのが面白いところですね。