y_uti のブログ

統計、機械学習、自然言語処理などに興味を持つエンジニアの技術ブログです

paiza オンラインハッカソン Lite のプログラム実装

paiza オンラインハッカソン Lite のプログラムを実装しました。ソースコードGitHub で公開しています。もともと、プログラムの動作確認用に n = 10,000 までのサンプルデータを作成したのですが、作成したデータの答えが現実的な時間で得られるよう*1、私なりにアルゴリズムを工夫したうえで C++ で実装してみたものです。

オンラインハッカソンのウェブサイトに掲載されている「入力例 2」を例題として、概要を説明します。入力例 2 は以下のデータです。下請け会社 5 社で必要人数 250 を満たすものを探します。

250
5
35 3640
33 2706
98 9810
57 5472
95 7790

まず、初期値 (0, 0) を積みます。これは、まだどの会社にも発注していない状態での (人員数、発注金額) を意味します。グラフの横軸が人員数、縦軸が発注金額を表します。
f:id:y_uti:20140810182239p:plain

最初の下請け会社は (35, 3640) です。ここでの選択肢として、この会社に発注する場合と発注しない場合の二通りがあります。発注する場合は、現在の点 (0, 0) に (35, 3640) を加えた値になります。発注しない場合は、現在の点 (0, 0) がそのまま次の反復に引き継がれます。
f:id:y_uti:20140810182253p:plain

次の下請け会社は (33, 2706) です。前回の反復で得られている (0, 0) と (35, 3640) のそれぞれについて、この会社に発注する場合と発注しない場合で枝分かれします。
f:id:y_uti:20140810182300p:plain

残りの各下請け会社についても、同様に枝分かれさせながら反復処理を進めていきます。
f:id:y_uti:20140810182306p:plain
f:id:y_uti:20140810182314p:plain

5 番目の下請け会社 (95, 7790) まで処理を進めたところで、必要人数である 250 人に到達する点がいくつか見つかります。このうち発注金額が最小のものが、ここまでの反復処理での最良解になります。通常はこの後も反復処理を続けますが、この例題では、これが最後の下請け会社なので、ここで反復処理が終了して全体の最良解 23,072 が得られます。
f:id:y_uti:20140810182319p:plain

さて、この処理を単純に進めると、反復ごとに場合の数が倍々に増えてしまいます。これでは n が大きくなったときに計算時間がかかりすぎるので、枝刈りによって効率的に計算を進める必要があります。私の実装では、次の 3 パターンの枝刈りを行っています。

  1. 発注金額が現在得られている最良解以上になった点は、候補から外す
  2. 残りの全社に発注しても必要人数に到達できない点は、候補から外す
  3. グラフ上で、ある点 A が別のある点 B の左上にあれば、点 A を候補から外す*2

さらに、できるだけ早い段階で候補の点をグラフの右側に押しやりたいので、入力データの下請け会社を人数の降順にソートします。また、残りの全社に発注した場合の合計人数は、最初にまとめて計算しておきます。先ほどの入力例 2 にこれらの前処理を加えると、以下のようになります。3 列目の値は、その行の会社に発注せず、次の行以降の全社に発注した場合の合計人数です。

98 9810 220
95 7790 125
57 5472 68
35 3640 33
33 2706 0

これにしたがって処理を進めた場合を先ほどと同様に図示してみます。

まず、初期値 (0, 0) に対して (98, 9810) を考えます。この会社に発注しない場合、残り 4 社すべてに発注しても人数は 220 にしかなりません。これは必要人数の 250 に届かないので、この会社には必ず発注することになります。
f:id:y_uti:20140810182326p:plain

次の (95, 7790) も同様です。この会社に発注しなければ、残り 3 社すべてに発注しても 98 + 125 = 223 と必要人数に届かないので、この会社にも必ず発注します。
f:id:y_uti:20140810182332p:plain

次の (57, 5472) に発注すると、必要人数 250 を満たす解 (250, 23072) が得られます。これをここまでの最良解として記録しておきます。また、この会社については、発注しない場合でも 98 + 95 + 68 = 261 と必要人数に到達可能です。したがって、発注しない場合も候補に残しておきます。
f:id:y_uti:20140810182338p:plain

次の (35, 3640) には必ず発注する必要があります。
f:id:y_uti:20140810182439p:plain

最後の (33, 2706) にも必ず発注する必要があります。これで、必要人数を満たす解 (261, 23946) が得られますが、これは既に得られている最小金額 23,072 を下回らないので、破棄します。これで全体の処理が終わり、最良解 23,072 が得られました。枝刈りを行わない場合と比べて、候補を絞り込めていることがわかります。
f:id:y_uti:20140810182446p:plain

このプログラムで、サンプルデータの data_un_*.txt の計算に要した時間は以下のとおりです。横軸が下請け会社数、縦軸が所要時間 (秒) です。なお、実行は Core i5 1.8GHz のマシンで行いました*3
f:id:y_uti:20140810201655p:plain

*1:その時に実装していた PHP のコードでは、HHVM で実行しても数分の処理では n = 1,000 程度までしか計算できませんでした。

*2:点 A が点 B よりも「人数が少ないのに高い」という意味になります。

*3:仮想マシン上で実行しています。