「 今週のお題：アダムズ方式で議席数を計算して！」問題解答 ( CodeIQ )

CodeIQ

はじめに

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

codeiq.jp

問題

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

  • 選挙において、定員数、選挙区の数、各選挙区の人口が与えられるとき、「アダムズ方式」による、各選挙区への定員数の割り当てを決定する。
  • 「アダムズ方式」とは、ある適切な数で各人口を割って、その商 ( 小数点以下切り上げ ) を各定員数とする方式を指す。ただし、合計が所定の定員数になるようにする。
  • 入力の1行目は、定員数・選挙区の数がコンマ区切りで、2行目以降は各選挙区の人口が1行に1選挙区分ずつとなる。対応する選挙区の定員数を1行ずつ出力する。

解説

各人口$p_i$ に対して、基準の除数を $b$ とすると、「切り上げ」で計算することから、各定員$q_i$は、次の範囲に収まります。

$$ \frac{p_i}{b}\le q_i\lt \frac{p_i}{b}+1 $$

そうすると、選挙区数$n$、定員合計$Q$に対して

$$ \begin{eqnarray} &\, & \sum\frac{p_i}{b}\le q_i\lt \sum(\frac{p_i}{b}+1) \\ &\Leftrightarrow & \sum\frac{p_i}{b}\le Q\lt n+\sum\frac{p_i}{b} \\ &\Leftrightarrow & \frac{1}{Q}\sum p_i\le b \lt\frac{1}{Q-n}\sum p_i \end{eqnarray} $$

が成立します。

ということで、この範囲の$b$に対して、定員合計が丁度$Q$になる所を探せば済むことになります。

これを実装したのが次のRubyのコードです。

q,n,*r=$<.read.scan(/\d+/).map &:to_i
s=r.reduce &:+
puts (s/q..s/(q-n)).each{|b|t,*y=0;r.each{|x|t+=e=(x+b-1)/b;y<<e};t>q or break y}

探索について、単調 ( 非減少 ) な量が対象なので、二分探索の方がより速いとは思うのですが…。面倒なので線形でやっています。

終わりに

今回はgolf的なところはさっぱりでした。何か良い方法があるのでしょうか…?

(2016/6/21追記) g_m_kさんから教えていただきましたが、アダムズ方式はドント方式と大分似た方法で計算でき、それで文字数も縮まるようです。なんだか不思議ですね。

(追記終了)