CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第98回「オリンピックの開催地はどうやって決まる？」

CodeIQというサイトで問題に挑戦した記録です。

問題文を要約すると下記の通り

• オリンピックの開催地決定について「繰り返し最下位消去ルール」が使われる。これを用いた投票パターンについて考える。
  下記は問題文の引用

開催地の決定に使われるのが「繰り返し最下位消去ルール」です。
トップが過半数を超えると、1回の投票で決定します。
トップが過半数を取れない場合、最下位を除外してもう一度投票を行います。
過半数を得るまでこの方法で投票を繰り返します。

ここでは、最下位が複数になった場合は、最下位1つが決まるまで上記の逆の投票を行うことにします。
（つまり、最下位が過半数を超えると1回で決定、過半数が取れない場合、最上位を除外してもう一度投票）
なお、投票を行ったときにすべての候補が同数になることはないものとします。

(中略)

n 個の候補地について、十分多くの人が投票することを考えます。
1つの候補地が決まるまでに必要な投票パターンが何通りあるかを求めてください。

例えば、n = 3の場合、
・1回目で1つが過半数を超えて決定
・1回目で1つが脱落し、2回目で残り2つの決戦投票
・1回目で下位2つが並び、2回目で下位2つの投票、3回目で決選投票
の3パターンがあります。

• 標準入力から国の数nが与えられ、nの場合の投票パターンの総数を解答する。
• nの最大は7

方針

当初、問題文が理解できなかった。特に

最下位1つが決まるまで上記の逆の投票を行うことにします。

最下位が過半数を超えると1回で決定

最下位が過半数とはどういう事か、過半数を獲得すれば「最上位」では無いかと悩んだが、最下位が複数になった場合の「逆の投票」というのが、当選させる国に投票するのではなく、落選させたい国に投票する。
との意味と考えると辻褄があった。

そうすると、投票パターンは「決戦投票」と「最下位決定戦」があるが、そのいずれもで、

• 1国の過半数で終了。
• 単独最下位が存在し、国を1つ減らして同じ事の繰り返し。
• 同率最下位が複数存在し、同率最下位の国の中で最下位決定戦を行う。
  (2からその時の国の数-1まで。題意より全ての国が同じ得票数になる事は無いが、トップ1国を除く全ての国が同率最下位になる事はある為。)

のパターンに分岐する事になる。

よって、対象の国の数nの時のパターン数をとすると、下記の漸化式で表す事ができる。

となる。
これを用いて実装する。

実装

golf解 Ruby(49byte)

a,s=0,0;(gets.to_i-1).times{a=(s+1)*a+1;s+=a};p a

通常解 JavaScript (SpiderMonkey)

では、

Sponsored Link