CodeIQ：アダムズ方式で議席数を計算して！

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「アダムズ方式で議席数を計算して！」（CodeIQ）を参照してください。

問題の概要

問題を引用します。

衆院選挙制度改革法が成立し、「アダムズ方式」による議席数の割り当てが2020年の国勢調査に基づき用いられることが決まりました。
アダムズ方式は、各都道府県の人口を「ある同じ数値」で割って、その答えの合計が全国の議席数と同一になるように割る値を調整する計算方式です。
商が小数になる場合は切り上げることになっています。

例えば、250人、200人、150人の3つの県から10議席を選ぶとき、それぞれ65で割ると3.84…、3.07…、2.30…なので4,4,3となり合計が10になりません。
それぞれ75で割ると3.33…、2.66…、2なので4,3,2となりこれも合計が10になりません。
しかし、それぞれ70で割ると3.57…、2.85…、2.14…なので4,3,3となり合計が10になります。

標準入力の一行目に「議席数の合計」と「小選挙区の数」、二行目以降に小選挙区の数の分だけ人口が与えられます。
このとき、標準出力に各小選挙区の議席数を出力してください。

なお、人口として与えられる数は最大で1500万、小選挙区の数は最大で50とします。
「議席数の合計」「小選挙区の数」「人口」「割る数」のいずれも整数です。
※各小選挙区の議席数が一意に決まらないような入力は考えなくてもよいものとします。

【入出力サンプル】
標準入力

10,3
250
200
150

標準出力

4
3
3

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

def adams(seats, population)
	cand = population.reduce(0, :+)/seats
	mx = cand * 2
	mn = cand / 2

	sum = 0
	while sum != seats
		slist = []
		for n in population
			slist << (n.to_f / cand).ceil
		end

		sum = slist.reduce(0, :+)

		if sum > seats then
			mn = cand
			cand = (cand + mx)/2
		elsif sum < seats then
			mx = cand
			cand = (cand + mn)/2
		else
			return slist
		end

	end
end

def printResult(slist)
	for i in slist
		p i
	end
end

#main
ln = 0
population = []
while line = gets
	line.strip!
	if line.empty? then next
	elsif ln == 0 then seats, area = line.split(",").map{|v| v.to_i}
	else population << line.to_i
	end

	ln += 1
end

ret = adams(seats, population)
printResult(ret)

解説

話題がタイムリーでちょっと面白いです。
議席数が一意に定まらない場合を考慮しなくて良いので、プログラム自体はそれほど難しくありません。

2分法

人口の最大数が1500万なので総当たりはしんどいですが、例をみればヒントがあります。
例では65で割って合計議席数が足りないので次は75。75で割ったら合計議席数が超えてしまうので次は70というふうにしています。こういう風に、ある数で割って足りなければ大きな数で割り、今度は足りなければ最初の値との間で割る。次に超えてしまったら最初の値との間の値、足りなければ2回目の値との間の値で割る、……を繰り返すことで最終的に議席数ぴったりの値にすることができます。

adams()

プログラムの本体です。
引数は議席数（seats）、選挙区の人口のリスト（popolation）です。

最初に割り算をする候補値（cand）と最大値(mx)と最小値(mn)を決めます。
大体人口の平均くらいが候補に近い気がするのでcandは人口の平均値にします。
mxはその値で割った場合、必ず議席数が足りなくなる値、mnは反対に必ず議席数をオーバーする値にする必要があります。ちょっと極端な場合（[1000,1,1,1,1]のような場合）を考えてみるとmxは平均値の2倍、mnは半分にしておけば条件を満たすようなのでそのようにしました。

あとは「2分法」に書いた通りの処理をします。
まず、candで人口を割って議席数を求め、合計します（10〜16行目）。
合計議席数がseatsを超えていたら次の候補値を(mx+cand)/2にします。また、新たなcandで値が決まらなかった場合の再計算時に、今回のcand以下の値になることはないのでmnを今回のcandにして範囲を狭めます（17〜19行目）。
合計議席数が足りなかった場合はこの反対を行います（20〜22行目）。
合計議席数がseatsに等しかったら処理を終了します（23〜24行目）。

雑感

議席数が一意に定まらない場合、その候補を全て列挙せよ、というような問題なら結構難しかったと思います。候補を見つけてからさらに前後に探索することになるのでしょうが、総当たりで大丈夫かどうかはちょっとわかりません。