CodeIQ：オリンピックの開催地はどうやって決まる？

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「オリンピックの開催地はどうやって決まる？」（CodeIQ）を参照してください。

問題の概要

問題を引用します。

いよいよリオデジャネイロ・オリンピックまで約50日。カウントダウンが始まります。
オリンピックの開催地が決まるまでには、IOC委員による投票があります。
2016年のリオは4か国の中から3回の投票で決まりました。
2020年の東京は3か国の中から3回の投票でしたが、どうやって決まるのか再確認しましょう。

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

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

例えば、2016年のリオの場合は以下のような投票結果でした。

都市 1回目 2回目 3回目

リオデジャネイロ 26 46 66

マドリード 28 29 32

東京 22 20 -

シカゴ 18 - -

2020年の東京の場合は以下のような結果でした。

都市 1回目 2回目 3回目

東京 42 - 60

イスタンブール 26 49 36

マドリード 26 45 -

例えば、n = 3の場合、

1回目で1つが過半数を超えて決定

1回目で1つが脱落し、2回目で残り2つの決戦投票

1回目で下位2つが並び、2回目で下位2つの投票、3回目で決選投票

の3パターンがあります。

同様にn = 4の場合は16パターンがあります。
標準入力から n が与えられたとき、パターン数を標準出力に出力してください。
(n は最大で7とします。)

都市	1回目	2回目	3回目
リオデジャネイロ	26	46	66
マドリード	28	29	32
東京	22	20	-
シカゴ	18	-	-

都市	1回目	2回目	3回目
東京	42	-	60
イスタンブール	26	49	36
マドリード	26	45	-

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

# 要素番号は候補者数
$PATTERN = [0,1,1]

def solve(n)
	if n < 3 then return end

	# m候補の投票結果
	for m in 3..n
		fixed = 1			# 1回目で過半数になるパターン
		for r in 1..(m-1)	# 最下位の数がr人で際投票のパターン
			fixed += $PATTERN[r] * $PATTERN[m-1]
		end

		$PATTERN << fixed
	end

	return $PATTERN[n]
end

while line = gets
	line.strip!
	if line.empty? then next end
	n = line.to_i
	p solve(n)
end

解説

見るからに動的計画法（メモ化再帰）を使用するという問題です。
ですが数学的な要素の強い問題なのでパターンを解析しないとできません。

考え方

候補数4で考えてみるとわかりやすいと思います。

1パターンは最初で過半数になる場合です。
後のパターンは最下位を除いて際投票になります。この時のポイントは必ず2回目は候補地が1つ減るということです。いきなり2つ以上候補地が減ったりはしません。なので、一般化して考えると候補地を1減らして同じように計算するということを繰り返せば良いということがわかります。
候補地の数に対して開催地が決定するパターン数を求める関数をf(n)とすると、2回目はf(n-1)、3回目はf(n-2)、…となります。

最下位が同数で際投票になる場合を考えます。
1以上の候補地が最下位になる場合は残っている（候補地の数-1）です。最下位の候補地の得票数が同数になるためには最下位が2以上なければなりませんが、1以上として考えるのがちょっとしたポイントと思います。
最下位が確定する手順も最下位の候補地の数に対して同じ処理を適用したものになるので、最下位の数をrとすると最下位が決定するパターンはf(r)、決定した最下位を除いて際投票して開催地が決まるパターンは2回目ではf(r₀)*f(n-1)、3回目はf(r₁)*f(n-2)、…です。
これを全てのrに対して加算すれば合計のパターン数が求まります。

solve()

これをコードにしたのがsolve()です。
$PATTERNは添字が残りの候補地の数の場合に何パターンあるかをメモする領域です。候補地が0〜2の場合は初期値として与えておきます。候補地2の場合、1回で開催地が決定するので候補地3以上の場合とは異なるため2までを初期値とします。

動的計画法なので計算結果を再利用するため候補地の数が少ない方から結果を積み上げます。これが10〜17行目のループです。候補地3の場合に結果を求めてメモし、候補地4の2回目の投票パターンとしてその計算結果を再利用します。同様に候補地5以降の場合もそれ以前の計算結果を再利用します。

変数fixedは開催地が決定するパターン数で、毎回1パターン（最初で過半数に達した候補地がある）場合が1パターンあります。なのでループごとの初期値は1です。
12〜14行目のループで最下位が同数の場合を処理しています。得票数が同値の最下位の数は1〜その時点の（候補地の数-1）なのでそれだけのパターンをループします。
考え方に書いた通り、最下位が決定するまでのパターンは同じ処理を最下位の数に対して適用したものなので、$PATTERNの計算結果から最下位の数に相当する値を取得すればわかります。このパターン数にその時点の（候補地の数-1）のパターン数を掛けたものがその場合の他ターン数になるのでそれをすべてたし合わせます。

最終的にnまでのパターン数を計算し、$PATTERN[n]の値が答えになります。

雑感

ちなみにこのコードにはn≦2の時にnilを返してしまうというバグがあります。
コードを提出して採点待ちの間に気づいたのですがテストケースがn≧3だったのでテストをパスしてしまいました。