#DFS#BFS

貪欲法について

貪欲法の考え方と応用的な貪欲法の実装について

目次

貪欲法とは1つのルールに則って貪欲的にその場での最善を選択することを繰り返すというアルゴリズム設計法
ここではいくつかの典型的な貪欲法の問題を見ていく.

硬貨の問題

1円玉,5円玉,10円玉,50円玉,100円玉,500円玉が,それぞれC1,C5,C10,C50,C100,C500C_1,C_5,C_{10},C_{50},C_{100},C_{500}枚ずつある.できるだけ少ない枚数の硬貨でA円を支払う.何枚の硬貨が必要か求めなさい.ただし,硬貨の求め方は少なくとも1つ存在するとする.

金額の高い硬貨からできるだけ多く使っていくことで解ける.貪欲法のアルゴリズムは基本的に高速であり,性能が高いものが多い.ナップサック問題の一種と考えることもでき,また,動的計画法により解くこともできるが,貪欲法のほうがシンプルに解決できる.

const int v[6] = {1, 5, 10, 50, 100, 500};

int c[6];
int a;
for(int i = 0; i < 6; i++){
    cin >> c[i];
}
cin >> a;

int ans = 0;
for(int i = 5; i >= 0; i--){
    int t = min(a/v[i], c[i]);
    a -= t * v[i];
    ans += t;
}
cout << ans << "\n";

区間の問題

n個の仕事がある.各仕事は時間sis_i,に始まり,時間tit_i,に終わります.あなたは各仕事について参加するかしないかを選ばなければならない.仕事に参加するならば,その仕事の始めから終わりまで参加しなければならない.また,参加する仕事の時間帯が重なってはいけない.最大何個の仕事に参加できるか求めなさい.
制約:1≤n≤105, 1≤si<ti≤1091 \leq n \leq 10^5, ~ 1 \leq s_i < t_i \leq 10^9

この問題も貪欲法により解ける.しかし,貪欲法にも様々な方法がある.例えば,選べる仕事のうち,最も開始時間の早いものを選ぶ方法がある.
しかし,必ずしもうまくいくわけではない.他にも

  1. 選べる仕事のうち,終了時間が最も早いものを選ぶ.
  2. 選べる仕事のうち,時間が最も短いものを選ぶことを繰り返す.
  3. 選べる仕事のうち,その仕事を選んだ時に選べなくなるほかの仕事の数が最も少ないものを選ぶ.

正しいものは,1番目のアルゴリズムであり,2,3番目にはそれぞれ反例が存在する.

const int max_n = 100000;

int n;
cin >> n;
pair<int, int> work[max_n];

//pairは辞書順で比較される
//終了時間の早い順にするため,tをfirstに,sをsecondに置く
for(int i = 0; i < n; i++){
    cin >> work[i].second >> work[i].first;
}
sort(work.begin(), work.end());
int ans = 0;
//tは最後に選んだ仕事の終了時間
for(int i = 0; i < n; i++){
    //最後に選んだ仕事と次の仕事の開始時間がかぶってはダメなため
    if( t < work[i].second ){
        ans++;
        t = work[i].first;
    }
}
cout << ans << "\n";

このアルゴリズムが正しいことの証明を簡単に説明すると,
終了時間が最も早い仕事を選ぶことで,次に選べる仕事の開始時間に対する制約を最小限にできる.
実際,最適解において最初に選ばれる仕事をA,終了時間が最も早い仕事をBとする.このとき,Bの終了時間はAの終了時間以下である.したがって,Aの代わりにBを選んでも,残りの仕事の選択可能性は失われない.
よって,最初の仕事としてBを選んでも最適性は保たれる.同様の議論を残りの仕事に繰り返すことで,貪欲法の正しさが示される.

辞書順最小の問題

n文字の文字列sが与えられ,n文字の文字列tを作る.初めは,tは長さ0の文字列で,次のいずれかの操作が行える.

  • sの先頭を1文字消去し,tの末尾に追加する
  • sの末尾を1文字消去し,tの末尾に追加する

tが辞書順比較でできるだけ小さくなるようにtを作りなさい.
制約:1≤n≤2000,1 \leq n \leq 2000,文字列ssに含まれるのはローマ字の大文字のみ.

  • sの先頭と末尾のうち,辞書順で早いほうをtの末尾に追加していくことを繰り返す.

しかし,sの先頭と末尾の文字が同じ場合が定義されていない.さらにその場合,その文字の後にできるだけよい(早い)文字を使いたいため,次の文字も比較する必要がある.よって次のようにする

  • sとsを反転させた文字列s’を辞書順比較する.
  • sが小さい場合,sの先頭を1文字消去し,tの末尾に追加
  • s’が小さい場合,同上

辞書順比較は基本的に貪欲法が有効

int n;
string s;
string t = "";
cin >> n >> s;
//s'を作らなくてもいい
int a = 0, b = n - 1;
while( a <= b ){
    //左から見た場合と右から見た場合を比較
    bool left = false;
    for(int i = 0; i < a + 1; i++){
        if(s[a + i] < s[b - i]){
            left = ture;
            break;
        esle if(s[a + i] > s[b - i]){
            left = false;
            break;
        }
        }
    }
    if(left) t.push_back(s[a++]);
    else t.push_back(s[b--]); 
}
cout << t << "\n";

Saruman’s Army

Nこの点が直線上にある.点iの位置はXiX_iである.N個のうちいくつかの点を選び,それらの点にしるしをつける.N個すべての点について,距離がR以内の場所に印をつけられた点がなければならない.(自分の場所に印がついている場合は,距離を0として考える.)条件を満たすようにしながらできるだけ印をつける点を少なくしたい.何個の点に印をつける必要があるか.
制約:1≤N≤1000, 0≤R≤1000, 0≤Xi≤10001\leq N \leq 1000,~ 0 \leq R \leq 1000,~ 0\leq X_i \leq 1000

方針
左から考えていく.一番左の点について,その点から距離R以内のところに印のついて点がなければならない.そして,その点は一番左の点から距離R以内の点で最も遠いものでないといけない.このようにして印をつける点を選べば,あとは,印をつけた点から右にR以上離れている最初の点について繰り返すだけでよい.すべての点をカバーすれば終わる.

int n,r;
int x[1000];

sort(x.begin(), x.end());
int i = 0, ans = 0;
while(i < n){
    //s:カバーされていない一番左の点
    s = x[i];
    //sから距離Rを超える点まで進む
    while(i < n && x[i] <= s + r)i++;
    //p:新しく印をつける点の位置
    int p = x[i - 1];
    ans++;
    //pから距離rを超える点まで進む
    while(i < n && x[i] <= p + r)i++;
}
cout << ans << "\n";

Fence Repair

とても長い板からN個の板を切り出そうとしている.切り出そうとしている板の長さはL1,L2,…,LNL_1,L_2,\dots ,L_Nであり,元の板の長さからちょうどこれの合計になっている(つまり,Σi=0NLi=C\Sigma_{i=0}^{N} L_i = C)板を切断する際には,その板の長さの分だけのコストがかかる.最小のコストを求めよ.
制約:1≤N≤20000, 1≤Li≤20000(i=1,2,…,N)1\leq N\leq 20000,~ 1\leq L_i\leq 20000(i = 1,2,\dots,N)

方針
順番などがなく自由度が高い問題でとっかかりがつかみにくい問題となっている.しかし,特殊な貪欲法により解くことが出来る.まず.切り出し方は二分木に対応している.
今回は,葉の節点が切り出された板1つ1つに対応している.また,葉の節点の深さは,その部分が切断に関わった回数に等しいため,コストの合計は各葉の節点の
板の長さ×節点の深さ板の長さ×節点の深さ
の和に対応している.ここで,次のような性質がいえる.一番短い節点とその次に短い節点は兄弟としてよい.最適解において,一番短い節点は,最も深い葉の1つであるはずである.そして,その葉にはそな字深さの兄弟が存在するはずである.それは同様に最も深い葉であるため,そこを次に短い節点とする.
LiL_iが小さい順にソートされているとする.この時,一番短い板の長さはL1L_1次はL2L_2であり,これらが兄弟であったということは,これらは長さ(L1+L2)(L_1 + L_2)の板から切断されたということになる.切断の順番は自由なので,これが最後の切断とする.すると,この切断の前は(L1+L2),L3,…,LN(L_1 + L_2),L_3,\dots,L_NのN-1本の板になっている同様のことを繰り返して再帰的にこのN-1本の問題とすると解が求まる.つまりは逆の作業をするわけである.これを実直に実装するとO(N2)O(N^2)となるがこの問題の場合は制限内に溶ける.しかし,O(Nlog N)O(Nlog~N)で解くこともできる.これは2-4で扱う.

using ll = long long;

int n,l[20000];

ll ans = 0;
//いたが1本になるまで
while(n > 1){
    //一番短い板min1,min2を求める.
    //sortじゃなくてした2つを探してくる.
    int min1 = 0,min2 = 1;
    if(l[min1] > l[min2])swap(min1,min2);
    for(int i = 2; i < n; i++){
        if(l[i] < l[min1]){
            min2 = min1;
            min1 = i;
        }
        else if(l[i] < l[min2])min2 = i;
    }

//min1,min2番目の板を結合
int t = l[min1] + l[min2];
ans += t;

if(min1 == n - 1)swap(min1, min2);
//min1,min2番目の数は用済みなので有効利用
//min1番目は,結合した値に
//min2番目は,一番最後の値をコピー.これにより探索範囲をn-1にできる.
l[min1] = t;
l[min2] = l[n - 1];
n--;
}
cout << ans << "\n";