貪欲法

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

目次

1. 硬貨の問題
2. 区間の問題
3. 辞書順最小の問題
4. Saruman's Army
5. Fence Repair

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

    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";
    

この問題も貪欲法により解ける．しかし，貪欲法にも様々な方法がある．例えば，選べる仕事のうち，最も開始時間の早いものを選ぶ方法がある．
しかし，必ずしもうまくいくわけではない．他にも 1. 選べる仕事のうち，終了時間が最も早いものを選ぶ． 1. 選べる仕事のうち，時間が最も短いものを選ぶことを繰り返す． 1. 選べる仕事のうち，その仕事を選んだ時に選べなくなるほかの仕事の数が最も少ないものを選ぶ．

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

    const int max_n = 100000;

    int n;
    cin >> n;
    pair 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";
    

このアルゴリズムが正しいことの証明は， 他の任にの選び方に対し，このアルゴリズムの選び方は，開始時間が早いものから同じ個数のところで，終了時間が遅くない．そのため，多く選べる選び方は存在しない．

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

しかし，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";
    

方針：
左から考えていく．一番左の点について，その点から距離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";
    

方針：
順番などがなく自由度が高い問題でとっかかりがつかみにくい問題となっている．しかし，特殊な貪欲法により解くことが出来る．まず．切り出し方は二分木に対応している． 今回は，葉の節点が切り出された板1つ1つに対応している．また，葉の節点の深さは，その部分が切断に関わった回数に等しいため，コストの合計は各葉の節点の

板の長さ×節点の深さ

    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";