CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第97回「アダムズ方式で議席数を計算して！」

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

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

• 選挙における議席数の割り当て方法に「アダムズ方式」がある
• 「アダムズ方式」とは、各選挙区の人口をある特定の数値で割り、その商の合計が議席数の合計に一致する様に特定の数値を調整するもの。
  割り算の際、商の少数点以下は切り上げる。
  （切り上げる事により、議員がゼロ人になる選挙区は無くなり、人口の少ない選挙区に有利になる）
• 標準入力から、1行目に議席数の合計、選挙区の数が、2行目以降にそれぞれの選挙区の人口が与えられる。
  アダムズ方式で計算したそれぞれの選挙区に割り当てられた議席数を改行区切りで解答する。
• 総人口の最大は1500万人、選挙区の最大は50、一意に決まらないテストケースはない。

方針

議席数の合計をn、人口の合計をmとする。
割る数dの初期値をm/nに設定し、各選挙区の人口をdで割り、少数部を切り上げたものの合計を計算する。
その合計がnより大きければ、dを大きくし、
その合計がnより小さければ、dを小さくして
合計がnと一致するまでこの計算を繰り返す。

この探索に高速化の為、二分探索を使用する。
（結果的には1つずつインクリメントする線形探索でも十分なサイズではあったが、二分探索で全てのケースで0.0秒だった）

但し、二分探索では、範囲が決められていない場合、探索する範囲を正しく設定しないと正しい結果が得られない

今回、特に根拠は無かったが、dの上限をdの2倍とした。
の二分探索では上限を10倍にしても100倍にしても実行時間はほとんど変わらないが、あえて2倍とした。
理由は、選挙区ごとの人口の偏り方により、割る数が10〜20%程度の変動でも、人口と議席数の比率の違い、「一票の格差」が数倍になる場合もあると考えた為である。
今回のテストケースでは全て2倍で正しく計算できた。

実装 (Ruby)

では、

Sponsored Link