この記事の内容

C++における整列の使い方と整列を利用したアルゴリズムである貪欲法について説明します。

整列

数値と文字列の整列

C++では、標準関数（STLの関数）として、sortが用意されています。整列に要する計算量は、列の長さを $N$ として $O(NlogN)$ です。

#include <algorithm>
#include <iostream>
using namespace std;
int A[5] = {3,5,1,2,4};
int main() {
sort(A,A+5); // 半開区間 [l,r) で指定する．sort(&A[0], &A[5]) と同じ意味
cout << A << endl;
}

配列を整列させる範囲を指定するには、&A[0]のように配列の要素を指すポインタを用います。一次元配列の場合には、単に Aと書くだけで、先頭要素を表すポインタに自動的に変換されます。つまり、sort(A,A+5)はsort(&A[0],&A[5])と同じ意味で、A[0]からA[4]まで（端点含む）が整列されます。

文字列の整列

標準ライブラリのsort関数は、数値だけではなく文字列stringの整列を行うこともできます。（一般に、比較演算子>が定義されている要素の配列が可能です。）
注意点としては、辞書式順序は、大文字小文字が混ざる場合は、C++のstd::stringの比較演算子の比較順序とは異なります。

ペアと整列

二つの要素が組みになっているようなデータ構造をペアといいます。整数のペアは以下のような構造体を用いて表現できます。

structure pair {
    int first;
    int second;
};

また、これと同様の使い勝手のいい、標準関数としてpairが用意されています。例えば、整数intのpairは、pair<int, int>で表現され、intをほかの型に置きかえれば、他のペアも利用可能です。通常はこちらの利用が推奨されます。また、ペアの二つの要素を同時に初期化する方法として、make-pairが用意されています。

pairのsort

ペアの配列も整列することができます。標準では、第一要素が異なるときは第一要素で順序が決まり、第一要素が同じときは第二要素で順序が比較されます。

#include <utility> // pair のため
#include <algorithm> // sort のため
#include <iostream>
using namespace std;
int main() {
pair<int,int> a[3]; // 整数のペア
a[0] = make_pair(170,60);
a[1] = make_pair(180,90);
a[2] = make_pair(170,65);

for (int i=0; i<3; ++i) // a[0] から a[2] まで表示
cout << a[i].first << ’ ’ << a[i].second << endl;
// 170 60
// 180 90
// 170 65 と表示されるはず

sort(a, a+3); // a[0] から a[2] まで整列

for (int i=0; i<3; ++i) // a[0] から a[2] まで表示
cout << a[i].first << ’ ’ << a[i].second << endl;
// 170 60
// 170 65
// 180 90 と表示されるはず
}

貪欲法

整列の重要な応用例として、貪欲法があります。貪欲法とは、組み合わせを考えることなく、単独の値を順にひとつずつみて、閾値を超えるまで、節約するすることを貪欲に決める方法です。

問題例

問題

護衛を上手に雇って，道中に襲われる人数の期待値を最小化する．護衛は 1 単位距離あたり 1
の金額で，予算がある限り，自由に雇える．
入力は，区間の数 N, 予算 M に続いて，距離と 1 単位距離あたりの襲撃回数の期待値のペア
⟨D,P⟩ が N 個.
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2019

解答の方針（貪欲法）
せっかく護衛を雇うなら，もっとも危険な区間を守ってもらうのが良いです。なので、一番危険な道を選び，予算がある限りそこに護衛を雇います。予算の残額で道の区間全てをカバーできない場合は、安全になる区間と、危険なままの区間が生じます。予算が残っている限り，2 番目に危険な道，3 番目に危険な道の順に同様に護衛を配置していきます。残った危険な区間についての襲撃回数の期待値の和が答えとなります。この計算課程では，⟨ 危険度, 長さ ⟩ のペアで道を表現し，危険な順に整列しておくと便利です。 (ここで危険度は，距離 1 移動する間に襲われる回数の期待値を表します。)

区間スケジューリング

貪欲法の応用で、区間スケジューリングというアルゴリズムを紹介します。

問題設定

一つの共有資源（例えば体育館など）と、多数の利用申請（開始時刻と終了時刻もペア）があったとします。このとき、利用時間が重ならないという条件の下で最大いくつの申請を受けられるでしょうか。

問題の単純化

体育館や時刻といった具体的なものをとると、これは、多数の線分の集合から重なりが空集合であるという条件の下で、最大の部分集合をとるという問題になります。

アルゴリズム

この問題は、以下の手順によって解くことができます。
1. 右端が一番左にある線分（＝早く終わる申請）を選び、重なる部分とともに取り除きます。（線分の対称性から、左端が一番右にある線分から消していく方法でも大丈夫です。）
2. 未選択の線分があれば、1.を繰り返します。

From Kawagoe

整列と貪欲法