Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の4_D問題をC++で解いてみました。
ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#4「探索」は、線形探索、二分探索、ハッシュ（辞書）を学びます。
問題（4_D: Allocation）
問題はリンク先をご覧ください。
解の二分探索について学びます。
解の二分探索について
具体的なプログラムは、めぐる式と呼ばれる二分探索の実装を参考にしました。
次のコードパターンを使います。
- 関数 is_OK: 正しい条件を判定するように実装する。
- 関数 my_search: 二分探索を行う。
- 変数 ok は、条件を満たす値を設定します。この値は条件を満たす値の最大（もしくは最小）である必要があります。
- 変数 ng は、条件を満たさない値を設定します。
関数 my_search 内の変数 ng と ok は、半開区間 [ok, ng) を表しています。この区間の長さが1回の繰り返しで半分になり、ok と ng の差が 1 になれば終了となります。ok が調べたい値となります。
bool is_OK(int mid, int key)
{
return true;
}
int my_search(int key)
{
int ng = 0;
int ok = 1000000000;
while (abs(ok - ng) > 1) {
int mid = (ok + ng) / 2;
if (is_OK(mid, key)) {
ok = mid;
} else {
ng = mid;
}
}
return ok;
}問題でも、このコードパターンを使います。
C++ プログラム例（ALDS1 4_D）
コードパターンを以下のように具体化します。
- 関数 is_ok: 引数はひとつとして最大積載量を与えます。$n$ 個の荷物 $w_i$ をトラックに積んでいき、必要なトラックの台数が $k$ 以下であれば true を、$k$ を超えれば、false を返します。
- 関数 my_search: main の中に取り込みました。ok には、$n$ の最大値と $w_i$ の最大値を掛けた $10^9$ を設定しました。ng には、0 を設定します（1 は条件を満たす可能性があります）。
以下が、C++プログラムとなります。
#include <iostream>
#include <vector>
using namespace std;
int n, k;
vector<int> w;
bool is_OK(int mid)
{
int this_k = 0;
int remain = mid;
for (int i = 0; i < n; ++i) {
if (w[i] > mid) {
return false;
}
if (w[i] <= remain) {
remain -= w[i];
} else {
++this_k;
remain = mid - w[i];
}
}
++this_k;
return this_k <= k;
}
int main()
{
cin >> n >> k;
for (int i = 0; i < n; ++i) {
int t;
cin >> t;
w.push_back(t);
}
int ng = 0;
int ok = 1000000000;
while (abs(ok - ng) > 1) {
int mid = (ok + ng) / 2;
if (is_OK(mid)) {
ok = mid;
} else {
ng = mid;
}
}
cout << ok << endl;
return 0;
}上のプログラムでは、最大積載量のトラックに積めるだけ荷物を積んでトラックが $k$ 台以下か判定しました。関数 is_ok は以下の別バージョンもあります。こちらは、$k$ 台のトラックに荷物を次々と積んでいき $n$ 個詰めるかを判定しています。
関数 is_ok 以外は変更していません。
#include <iostream>
#include <vector>
using namespace std;
int n, k;
vector<int> w;
bool is_OK(int mid)
{
int i = 0;
for (int j = 0; j < k; ++j) {
int s = 0;
while (s + w[i] <= mid) {
s += w[i];
++i;
if (i == n) {
return true;
}
}
}
return false;
}
int main()
{
cin >> n >> k;
for (int i = 0; i < n; ++i) {
int t;
cin >> t;
w.push_back(t);
}
int ng = 0;
int ok = 1000000000;
while (abs(ok - ng) > 1) {
int mid = (ok + ng) / 2;
if (is_OK(mid)) {
ok = mid;
} else {
ng = mid;
}
}
cout << ok << endl;
return 0;
}上記プログラムは、どちらも AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
トピック#4では、探索について学びました。特に値の二分探索（4_B）と解の二分探索（この記事）は応用範囲が広い考え方です。
引き続き、ALDS1 の問題を紹介していきます。
