もし先輩女子エンジニアが『アルゴリズム』を図解で教えてくれるとしたら

2014年7月30日より8月27日まで開催した、paizaオンラインハッカソン（略してPOH![ポー！]）Lite「天才火消しエンジニア霧島　もしPMおじさんが『丸投げ』を覚えたら」ですが、どのような解法が有ったのでしょうか。

今回もPOH恒例の「解説図解」を、天才火消しエンジニア霧島が解説するとしたら、という体で書いてみたいと思います。(特に文体とか変えませんがｗ 最後に霧島壁紙DLが有るので是非最後までお読みください。)

■どのような高速化ステップがあるのか？

今回の問題ですが、実行時間に大きく影響する計算量別にみたアプローチでは、すべての組み合わせを出して、人数を満たして一番安い組み合わせを見つける全探索[計算量はO(2^N)]と、動的計画法[計算量はq = max(q_i) としてO(Nq) ]（やり方によってはO(NM)）による2種類があります。

また全探索を改良し、効率的な枝刈り（無駄な組み合わせをスキップする）やりかたによって、計算量は大きく変えず定数倍高速化する方法があります。こちらのやり方は全探索と動的計画法の中間的な実行速度になります。

◆実行速度順位

1. 動的計画法
2. 全探索枝刈り
3. 全探索

今回は全探索（再帰、ビット演算の2種類）と動的計画法の計３種類の解法について解説をしたいと思います。

※O(2^N)というような書き方は、その解法のオーダー（計算量）を表す書き方です。よくわからない、という方はランダウの記号について読んでみてください。

■問題文の再確認

まずは問題文の確認をしてみましょう。

あなた(霧島京子) は20万人月の巨大なプロジェクトを一ヶ月で終わらせるために無数の下請け会社から人員をかき集める仕事をすることになりました。
プロジェクトを終わらせるのに必要な人員数 m 名 と、発注可能な下請け会社の数 n 社、各下請け会社のアサイン可能なエンジニア人員数 q_i 名 と、発注に必要な費用 r_i 万円が与えられます。

各下請け会社の人員は、一部を使うなどは出来ず全員を使わなくてはいけません。
プロジェクトに必要な人員数 m 以上を満たせる組み合わせで、最も安くすむ合計金額(単位：万円)を出力してください。
各下請け会社の人員数の合計はプロジェクトの規模 m 人月以上になるものとします。

出題ページ
paizaオンラインハッカソン（略してPOH![ポー！]）Lite「天才火消しエンジニア霧島　もしPMおじさんが『丸投げ』を覚えたら」

■全探索O(2^n)の解法

この解法は各下請け会社について全ての組み合わせを計算し、最も安く条件を満たせるものを探します。すべての会社数 n について使う、使わないの二択をするために 2^n の組み合わせを試していく事になります。

この解法では n が一つ増えるたびに計算量が倍になってしまい、n の数が増えると計算量が莫大になりタイムアウトしてしまいます。そのためこの解法ではテストケース6（n = 45）を通すことが出来ません。（テストケース5はn = 10）

◆全探索の計算量

全探索の計算量を見ていくとn が増えるたびに下記の様に計算量が増えていきます。
n=2だと2^2 = 4 の組み合わせ
n=3だと2^3 = 8 の組み合わせ
n=4だと2^4 = 16 の組み合わせ
n=5だと2^5 = 32 の組み合わせ
n=6だと2^6 = 64 の組み合わせ
.
.
n=45だと2^45 = 35,184,372,088,832 の組み合わせ
n=50だと2^50 = 1,125,899,906,842,624 の組み合わせ

n (下請け候補の会社数)の最大値は50社ですが、50社になると組み合わせは1,125,899,906,842,624通りと巨大になるため、全探索法だとタイムアウトしてしまいます。実際に20万人月のプロジェクトを回すとしたら50社以上かかる気がしますが。。

◆全探索の処理手順

全探索の処理手順はざっくりというと下記の様になります。

1. 各会社に関して使う使わないの全組み合わせリストを生成する
2. リストに従って必要な人員数 m を満たせるかを計算し、コストを記録する
3. もっとも低いコストになって人員数mを満たせる数値を出力する

全組み合わせリストを図解すると下記のようになります。

今回の問題は問題文としてはとてもシンプルですが、手順1の全組み合わせリストを生成する部分は、プログラミング初心者にとっては少し頭を使う必要がある部分となります。

ベタにこれをfor文だけで実装すると、マンガで出てきたような火村氏が書いているようなコードになってしまいます。

これをスマートに書く方法は幾つかありますが、ここでは再帰による解法と、よりスマートな(？)ビット演算による解法を紹介します。

◆1. 再帰による解法

再帰（再帰呼出し）とは，ある関数が自分自身を呼び出すことで、フォルダ／ディレクトリ全体を舐めるような場合、釣銭の組み合わせを求める場合などの事前に処理対象全体がつかめず、かつ処理する内容が同じ、というような場合に便利な書き方です。

今回の問題のように与えられる社数がケース毎に可変し、その組み合わせを求めるような場合は、再帰を使えばfor文の入れ子を使わなくても書けるため、コードの見通しが良くなります。

ただ再帰呼出しを使うとはコードの見通しは良くなりますが、計算量が減るわけではなく、むしろ関数のオーバーヘッドで非効率になったり、ネストが深くなりすぎてスタックオーバーフローなどの問題が起きがちなので注意が必要です。

再帰呼出しのコード（Ruby）

def calc(cost, staff, idx)
 return if @n <= idx
 if @m <= staff + @companies[idx][0]
   @results << cost + @companies[idx][1]
 else
   calc(@companies[idx][1] + cost, @companies[idx][0] + staff, idx + 1)
 end
 calc(cost, staff, idx + 1)
end

@m = gets.to_i
@n = gets.to_i

@companies = []
@n.times do
 @companies << gets.split.map(&:to_i)
end

@results = []
calc(0, 0, 0)
puts @results.sort.first

◆2. ビット演算による解法

ビット演算による解法は、それぞれの下請け会社を使う、使わないを0、1の2進数として考えて2^nまでの10進数を2進数に変換してすべての組み合わせパターンを出すという方法です。

具体的にはn =3社とした場合、組み合わせ数は 2^3 = 8 なので8パターンという事なります。0～7の10進数(8パターン)を2進数に変換すると下記のようになります。

10進数	2進数(0埋め3桁)
0	000
1	001
2	010
3	011
4	100
5	101
6	110
7	111

このように0,1の全パターンが列挙することが出来ます。2進数の各桁を各会社と置き1ならば使う、0ならば使わないと言う形で計算をして最も安い条件を探索していきます。

一桁目をA社、二桁目をB社、三桁目をC社とすると、例えば「011」はA,B社を使い、C社を使わないパターンとなります。この方法なら一つのfor文で全組み合わせを算出する事が出来ます。

ビット演算のコード（Ruby）

Ruby以外の言語(Java,PHP,Perl,Python,JavaScript.C,C++,C#)のコードはpaiza会員ページにて公開しています。
⇒他言語のコードを見る（会員登録が必要）

# coding: utf-8
m = gets.to_i
n = gets.to_i
qr = []
n.times do
  tmp = gets.split(" ")
  qr.push([tmp[0].to_i, tmp[1].to_i])
end

#m社のうちi番目の会社を使うか使わないかの表を作る
#3社とかなら
# A, B, C
# 1, 1, 1
# 1, 1, 0
# 1, 0, 1
#.....続く...
#みたいな1を使う0は使わないの表を作る

use_list = []

#2進数で考えると
(2**n).times do |i|
  use_list.push((("%0" + n.to_s + "d") % i.to_s(2)).chars.map {|c| c.to_i})
end

#使う使わないリストから、人月を満たせる組み合わせで最安を探す
ans = qr.map { |i| i[1] }.inject(:+)
use_list.each do |i|
  cost = 0;
  ningetsu = 0;
  i.each_with_index do |v, j|
    if v == 1
      ningetsu += qr[j][0]
      cost += qr[j][1]
    end
    if ningetsu >= m and ans > cost
      ans = cost
    end
  end
end

print ans, "\n"

■動的計画法による解法 [q = max(q_i) として、O(Nq) ]

動的計画法とは、対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録し、再利用ながら解いていくアルゴリズムです。この方法を使えば、全探索ではO(2^n)だったものがO(Nq)に高速化する事ができます。

今回の問題では、企業を順番に増やしていきながら、合計人数毎の最低金額を記録しておく事で、同じ計算をしないですむ様にしていきます。

◆手順

1. 与えられた企業に対してループ
   1. メモ配列（合計人数と最安費用のメモ）に対してループ
      1. 処理中の企業の人数＋メモ配列の人数　の合計人数のメモ配列を参照
      2. 最安費用が格納されてなければ、処理中の企業の費用＋メモの最安費用を格納
      3. 最安費用が格納されていたら、比較をして安い方を格納
2. 必要人数以上で一番安い金額を出力

※解説しやすい手順としているので若干プログラム的には不自然になっています。点順が理解できたらより分岐の少ない書き方を考えてみてください。

◆手順詳細

ここでは小さな入力例として下記のような入力を考えます。

3 // 必要人数
4 // 入力社数
1 100 // A社 1名：100万円
2 110 // B社 2名：110万円
3 320 // C社 3名：320万円
4 300 // D社 4名：300万円

動的計画法では計算結果を格納して再利用するので、まず再利用する為の入れ物を作ります。何を格納するかは考え方によりますが、ここでは合計人数と、その合計人数における最安費用を格納する入れ物を作りる事にします。

その入れ物にまずA社（1名、100万円）を格納すると、合計人数1人：最安費用100万円となります（上記図）。

次にB社に付いての処理を行ないます。処理としては会社順に該当人数の箇所に最安値を当てはめていきますが、既に格納されている値が有る場合（この場合は1人100万円）は、格納済みの値に、これから処理する人数と費用を合計する計算も行ないます。

具体的には1人（A社の値）の欄に格納されている最低金額とB社（2名、110万円）の2人の合計金額=3人の価格も計算をして3人の最安費用（A社1名100万円＋B社2名110万円=3名210万円）を格納します。次に2人の最安費用の部分にB社の価格である110万円を格納します。1人の部分はとくに変更がないのでそのままです。（下記図）

そして、C社（3名、320万円）はどうでしょうか？　既に最安値が入っている1〜3人にC社の3名を足した4~6人の最安費用に、それぞれの合計費用を入れていきます。1人＋3人（C社）=4人は420万円、2人＋3人（C社）=5人は430万、3人＋3人（C社）=6人は530万です。
1人、2人は特に変更がないのでそのままです。3人の最安費用はすでに210万円（A社＋B社の価格）が格納されており、C社の320万円とバティングします。ここが動的計画法のポイントですが、後に３人＋○人のような計算をするときに、３人の価格計算（この場合は１人＋２人と３人の2パターン）を最良のパターンのみにまとめておく事で計算量を減らします。今回は最安値を求めるため、この場合は安い方を優先して格納します。この場合は210万円が安いのでそちらを格納します（210万円はすでに格納されている値なので、実際のプログラム的には変更は加えません）。（下記図）

D社についても同様に処理をします。4〜6人の部分で既に格納されている値とバッティングするため、それぞれ比較し最安の方を格納します。

このように合計人数ごとに最安費用を計算していき、過去の計算結果を利用する事で計算量を減らす事が出来ます。このやり方であれば、社数分のループ×格納されている値分のループ(最大で全社の合計人数分のループ)で終わる事になります。

ここに示した図を理解できれば、コード量もさほど長くなく30分もかからず組める内容かと思いますので、動的計画法で書けていなかったという方は是非チャレンジしてみてください。ただ読むだけよりも実際に書いてみた方が明らかに力になると思います。実行はPOH Liteのページで引き続き可能です。

今回の問題は知っている人も多いと思いますが、ナップサック問題の変形版でした。興味を持たれた方はナップサック問題にも是非チャレンジしてみてください。

動的計画法のサンプルコード（Ruby）

Ruby以外の言語(Java,PHP,Perl,Python,JavaScript)のコードはpaiza会員ページにて公開しています。⇒他言語のコードを見る（会員登録が必要）

#coding: utf-8

M = gets.to_i #必要人数
N = gets.to_i #入力社数

min_cost = 0
q = Array.new(N)
r = Array.new(N)
# q 各下請け会社の人員数
# r 各下請け会社への発注費用
N.times do |i|
  q_t, r_t = gets.split(" ").map {|s| s.to_i}
  q[i] = q_t
  r[i] = r_t
  min_cost += r_t
end

dp = Hash.new
dp[0] = 0
# dp[人数] = 最低価格

# 入力社数分のループ
N.times do |i|
  dp_tmp = dp.clone
  # 人数ループ
  dp.each do |key, value|
    total_q = key + q[i]
    total_r = value + r[i]
    if dp_tmp.has_key?(total_q) == false
      dp_tmp[total_q] = total_r
    else
      if dp_tmp[total_q] > total_r
        dp_tmp[total_q] = total_r
      end
    end

    if total_q >= M && min_cost > total_r
      min_cost = total_r
    end

  end
  dp = dp_tmp

end

p min_cost

■まとめ

今回は動的計画法か、枝刈りをきっちりやれば満点が取れ内容でしたが、いかがでしたでしょうか。動的計画法はナップサック問題を知っていればそこから発想するのはそれほど難しく有りませんが、逆にナップサック問題を知らないと動的計画法にたどり着くには少し難しかったかもしれません。ただ一度動的計画法を覚えてしまえば、これは動的計画法で解けるかも？とひらめく事が出来ますので是非覚えてみてください。paizaではこのほかにも色々な問題を用意しているのでご興味が有る方は覗いてみてください！

paizaオンラインハッカソンのレポートは今回で終了ですが、次回開催の準備も進めておりますので是非次回も皆様のご参加をお待ちしております！

■おまけ

最後まで読んでいただきありがとうございました。霧島壁紙を作りましたのでよろしければお使いください！

天才火消しエンジニア霧島壁紙_2560x1600
天才火消しエンジニア霧島壁紙_1024x768

---

paizaは、技術を追い続けることが仕事につながり、スキルのある人がきちんと評価される場を作ることで、日本のITエンジニアの地位向上を目指したいと考えています。

「paiza転職」は、自分のプログラミング力が他社で通用するか（こっそり）腕試しができる、IT／Webエンジニアのための転職サービスです。プログラミングスキルチェック（コーディングのテスト）を受けて、スコアが一定基準を超えれば、書類選考なしで複数の会社へ応募ができます。

まずはスキルチェックだけ、という使い方もできます。すぐには転職を考えていない方でも、自分のプログラミングスキルを客観的に知ることができますので、興味がある方はぜひ一度ご覧ください。

また、paiza転職をご利用いただいている企業の人事担当や、paiza転職を使って転職を成功した方々へのインタビューもございます。こちらもぜひチェックしてみてください。
詳しくはこちら