イノベーション エンジニアブログ


株式会社イノベーションのエンジニアたちの技術系ブログです。ITトレンド・List Finderの開発をベースに、業務外での技術研究などもブログとして発信していってます!


このエントリーをはてなブックマークに追加

社内で行われた第一回アルゴリズム大会で優勝しました!

どうも、Anti-Pattern初代テックリードのbigenです。
先日、社内で第一回アルゴリズム大会が開催されました。
社内エンジニアを対象に、参加者全員で同じ問題を解き、もっとも短い時間で解答を出力するコードを書いた人が優勝です。
なんとこの大会で僕が優勝しまして、初代テックリードの称号を頂きました。
数カ月後に第二回をするそうなので、次回も今から楽しみです。

今日はその大会で出題された問題について解説してみようと思います。

問題

各都道府県の人口が下記配列で与えられ、議席数の合計が289の時、アダムズ方式で各都道府県ごとの議席数を割り振る時、計算に用いる「各都道府県の人口を割る、ある整数」を求めよ。(制限時間30分くらい)

// 各都道府県の人口
$pref = [5381733, 1308265, 1279594, 2333899, 1023119, 1123891,
    1914039, 2916976, 1974255, 1973115, 7266534, 6222666,
    13515271, 9126214, 2304264, 1066328, 1154008, 786740,
    834930, 2098804, 2031903, 3700305, 7483128, 1815865,
    1412916, 2610353, 8839469, 5534800, 1364316, 963579,
    573441, 694352, 1921525, 2843990, 1404729, 755733,
    976263, 1385262, 728276, 5101556, 832832, 1377187,
    1786170, 1166338, 1104069, 1648177, 1433566];

※この問題は、次のURLの問題を参考に作成されています。アダムズ方式の計算方法についてもそちらを参照ください。
https://news.goo.ne.jp/article/codeiq/trend/codeiq-49286.html

考え方

「人口を割る、ある整数」をRとします。
Rが大きくなったり小さくなったり変化した時なにが起きるかを考えてみると、総議席数が変化することがわかります。

例1 ) R=10000のとき
// 各都道府源の議席数
$seats = [539, 131, 128, 234, 103, 113,
    192, 292, 198, 198, 727, 623,
    1352, 913, 231, 107, 116, 79,
    84, 210, 204, 371, 749, 182,
    142, 262, 884, 554, 137, 97,
    58, 70, 193, 285, 141, 76,
    98, 139, 73, 511, 84, 138,
    179, 117, 111, 165, 144];
// 総議席数
$total = count(seats); // 12734

例2 ) R=100000のとき
// 各都道府源の議席数
$seats = [54, 14, 13, 24, 11, 12,
    20, 30, 20, 20, 73, 63,
    136, 92, 24, 11, 12, 8,
    9, 22, 21, 38, 75, 19,
    15, 27, 89, 56, 14, 10,
    6, 8, 20, 29, 15, 8,
    10, 14, 8, 52, 9, 14,
    18, 12, 12, 17, 15];
// 総議席数
$total = count(seats); // 1299

ですので、今回の問題はRを順番に試していって、総議席数がぴったり289になるRを探すという探索問題だということがわかります。

しかも、総議席数はRに対して単調減少(Rを大きくすると、必ず総議席数は変わらないか小さくなる。増えることはない。)になっているので、リスト探索問題として扱えそうです。
つまり、

R

総議席数(単調減少なので、降順にソートされているのと同じ)

1

127094745

2

10000

12734

100000

1299

???

289

とソート済みのリストあるいはDBのようなものがあって、目的のRを発見すればよいということですね

リスト探索問題で代表的な解法は https://ja.wikipedia.org/wiki/%E6%8E%A2%E7%B4%A2#%E3%83%AA%E3%82%B9%E3%83%88%E6%8E%A2%E7%B4%A2 こちらを参照してください

細かなテクニック(おおまかなアタリをつけてからやるとか)は色々あるとして、大きな方針としては

  1. 線形探索

  2. 二分探索

のどちらかになるでしょう。今回のようにデータ量が多いリストを考える時は、ほぼ迷わず二分探索を選んでいいと思います。
線形探索の計算量は O(n)ですが、二分探索ではO(log n)だからです。

データ量が少ない探索であれば、テクニックを駆使した線形探索でも二分探索を上回る速さを出せることはありますが、データ量が多くなればなるほど、ちょっとやそっとで追いつけない計算量の差ができてしまいます。
計算量については過去のブログ( アルゴリズム計算量入門 〜 ①)でわりと詳細に触れています。

というわけで何も考えず二分探索で書いてみました。

二分探索とチューニング

adams.php
<?php
// number of seats
$n = 289;
// population of each prefecture
$pref = [5381733, 1308265, 1279594, 2333899, 1023119, 1123891,
    1914039, 2916976, 1974255, 1973115, 7266534, 6222666,
    13515271, 9126214, 2304264, 1066328, 1154008, 786740,
    834930, 2098804, 2031903, 3700305, 7483128, 1815865,
    1412916, 2610353, 8839469, 5534800, 1364316, 963579,
    573441, 694352, 1921525, 2843990, 1404729, 755733,
    976263, 1385262, 728276, 5101556, 832832, 1377187,
    1786170, 1166338, 1104069, 1648177, 1433566];

$start = microtime(true);

// main logic
$sum = array_sum($pref);

// initial span
$from = 1;
$to = $sum;

// binary search
while (true) {
    $mid = ceil(($from + $to) / 2);
    $seats = array_map(function ($value) use ($mid) {
        return ceil($value / $mid);
    }, $pref);

    $total = array_sum($seats);

    if ($total == $n) {
        $result = $mid;
        break;
    } elseif ($total < $n) {
        $to = $mid;
    } elseif ($total > $n) {
        $from = $mid;
    }
}


$end = microtime(true);

$interval = $end - $start;

echo "R: " . $result . "\n";
echo "interval: " . $interval . "\n";
echo "iteration: " . $i . "\n";

// R: 478528
// interval: 0.00014901161193848
// iteration: 18

というわけで、二分探索の範囲の初期値は余裕をもって1 ~ 総人口と適当において動かしてみると、
反復回数18回で約0.000149秒くらいでした。

なかなかいいスコアです。
「二分探索」というスキームで戦う以上は、あとは初期値くらいしかチューニングできないので、初期値を工夫してみます。


「答えって大体この辺に近そうだよね」という指標をまず考えてみます。
直感的に、人口をRで割ったあとの配列(切り上げる前)の合計が289になってると、切り上げたあとの合計も289に近そうです。 そしかも必ず289より大きくなります。

これをもとにちょろっと計算してみると、R=(総人口/289)とすると、総議席数は289~(289+47)の間にくることがわかりました。

例) 簡単のため、
$array = [10, 15, 25]
について考えると、配列の合計50で値を全部わると、
$array = [0.2, 0.3, 0.5]
となり、全て合計すると1になる配列になります。さらに全部に289をかけると、
$array = [57.8, 86.7, 144.5]
となり、合計すると289になる配列になります。
このあと各要素を切り上げていくんですが、その合計は289より大きくなってるのは自明ですね。

ちなみに、切り上げたときに増える議席数は1要素あたり0〜1の間でしか増えないはずです。
「(合計)で割って(289)をかける」のは「(合計/289)で割る」のと同じなので、Rを(合計/289)としておくと、総議席数は289~(289+3)の間にくるはずです。

同様に、R=(総人口/(289-47))とすると、総議席数は(289-47)~289の間に来ます。

これを使うと、総議席数が289となるようなRは、 (総人口/289) より大きく (総人口/(289-47)) より小さいということが分かるので、それを初期値として組み込んでみます。

$from = $sum / $n;
$to = $sum / ($n - count($pref));

...

echo "R: " . $result . "\n";
echo "interval: " . $interval . "\n";
echo "iteration: " . $i . "\n";

// R: 478644
// interval: 0.0000731945037841
// iteration: 9

というわけで反復回数をさらに半分にし、計算時間も半分になりました。

おわりに

大会の後から知ったんですが、探索点を中間点以外のところにとる 内挿探索 というアルゴリズムがあるそうで、
データの偏りが少ない今回のような問題ではかなり速度があげられそうです。

ロジックもそれほど複雑ではなく二分探索の延長で実装できそうなので、暇があれば挑戦してみようと思います。