蟻本練習問題の解説をします。今回のトピックは貪欲法です！

シリーズ目次はこちらからどうぞ。

猪突猛進！ "貪欲法"

区間

POJ 2376: Cleaning Shifts

区間が $N$ 個あり、 $i$ 番目の区間は $\left[ l_{i}, r_{i} \right]$ の閉区間である。これらの区間の中からいくつかを選び、 $\left[ 1, T \right]$ を全て被覆したい。そのようなことが可能であれば選ぶ区間の数の最小値を、不可能であれば $-1$ と答えよ。

▶表示する

直感的に、長い区間を使いながら被覆したい気持ちになります。どのように取っていけばよいでしょうか？

左から埋めていくことにしましょう。すべてを被覆する必要があるため、まずは明らかに地点 $1$ を被覆する必要があります。これは、選ぶべき区間の左端 $l_{i}$ が $\left[ 1, 1 \right]$ の中にある必要があるとも言えます。なので、 $l_{i}$ の値が $1$ であるような区間のうち、どれかを選ばなければいけません。複数ある場合は、より長い区間 ( $r_{i}$ の値が大きい区間) を取るほうが得になるため、それを選ぶことにします。

区間 $\left[ l_{f}, r_{f} \right]$ を $1$ つめの区間として選ぶと、当然 $\left[ l_{f}, r_{f} \right]$ が被覆されます。また、 $1$ つめの区間の左端は必ず $1$ なので、 $\left[1, r_{f} \right]$ が被覆されているとも言えます。

ここで、次の区間を選ぶことを考えましょう。選ぶべき区間の左端としてあり得る値は、 $\left[2, r_{f} + 1 \right]$ の範囲内へと変わりました (さきほど選んだ区間によって $1$ が既に被覆されていることから $1$ についてはもう考えなくてよいこと、さらに右端の値に $1$ 足したものも選べることに注意してください)。ここに属する区間のうち最も右端の値が大きいものを選ぶことで、最適な選び方ができます。

以上をまとめると、次のようになります。

選べる区間の左端の値の範囲を $\left[ l_{p}, r_{p} \right]$ として管理する。はじめは $l_{p} = 1, r_{p} = 1$ としておく。
区間の左端の値が $l_{p} \leq l_{i} \leq r_{p}$ となっているような区間 $i$ の中で、右端の値 $r_{i}$ が最大のものを取り、 $r_{new} = r + 1$ として覚えておく。
範囲内にある区間を全て見終わったら、 $l_{p}$ を $r_{p} + 1$ に、 $r_{p}$ を $r_{new}$ に更新する。
終端まで全てカバーするまでこれを繰り返す。途中で止まれば不可能。

int N, T;
pair<int, int> seg[30010];

int main() {
    scanf("%d%d", &N, &T);
    for(int i=0; i<N; i++) {
        int l, r; scanf("%d%d", &l, &r);
        seg[i] = make_pair(l, r);
    }

    sort(seg, seg+N);

    // 取って良い区間の左端は [l_p, r_p] の中に収まっている
    int idx = 0, l_p = 1, r_p = 1, r_new = -1, ans = 0;
    while(1) {
        bool updated = false;

        // 範囲内にある区間の中で、右端が最大であるものを取る
        for(; idx<N && seg[idx].first <= r_p; idx++) {
            if(r_p >= seg[idx].second + 1) continue;
            r_new = max(r_new, seg[idx].second + 1);
            updated = true;
        }
        ans += updated;
        
        // 全てカバーできれば OK
        if(r_new == T+1) {
            printf("%d\n", ans);
            return 0;
        }

        // 更新を反映させる。そもそも更新が起こっていなければ NG
        if(updated) {
            l_p = r_p + 1;
            r_p = r_new;
            r_new = -1;
        }
        else {
            printf("-1\n");
            return 0;
        }
    }

    // 最後までカバーできなければ不可能
    printf("-1\n");
    return 0;
}

POJ 1328: Radar Installation

問題リンク

2 次元平面上に点が $N$ 個ある。いくつかの円を用意して、全ての点を囲みたい (点が円周上にあっても、それは囲まれていると見なす)。円は半径が $d$ で固定であり、中心は必ず $x$ 軸上になければならない。このようなことが可能ならば用意する円の個数の最小値を、不可能であれば $-1$ を出力せよ。

▶表示する

半径が $d$ で固定で、しかも中心は $x$ 軸上になければならないことから、 $y$ 座標の絶対値が $d$ を超えるような点が存在する場合は、明らかに不可能です。そのような点がない場合は、いくつかの円を用意することですべて囲むことができます。

「点を円 $C$ で囲める」ということに関して、「点と円 $C$ の中心との距離が $d$ 以下である」が必要十分です。この条件を満たしながら最小化します。どうすれば良いでしょうか？

「点と円 $C$ の中心との距離が $d$ 以下」になるような、円 $C$ の $x$ 座標のとり得る値の範囲がどうなるかを考えましょう。これは図に描いてみると、上のように 1 つの連続した区間になっていることが分かります。このような区間が点の個数ぶん存在します。

円の個数を最小化したいので、この問題は「上で求めた区間からなるべく少ない個数だけ選んで、すべての区間について被るようにしたい」と言い換えられました。これはどう解けばよいでしょうか？実はこれは区間スケジューリング問題 (P43) と等価ですので、それを書けば終わりです。

なぜ区間スケジューリングと等価なのでしょうか？そもそも区間スケジューリング (以降 IS と略記) とは、「区間がたくさんあって、その中から overlap ようになるべく多く取る」というものでした。つまり、IS によって選ばれたものはそれぞれ overlap していないので、これらの区間は全て取らなければならず、IS によって得られた値よりも小さい値を達成することはできません。また、IS で選ばれていない区間は、選ばれた区間のいずれかと必ず overlap しているため、IS によって選ばれた区間を全て選ぶことによって、「すべての区間について被る」という条件を満たします。よって、IS で求めた値がこの問題の答えになっていることが言えます。

struct seg {
    double l, r;
    seg() {}
    seg(double a, double b) : l(a), r(b) {}
    bool operator<(const seg &e) const {
        if(r != e.r) return r < e.r;
        return l < e.l;
    }
};

pair<double, double> points[1010];
seg segments[1010];
int N, D;

seg calc_x(int idx) {
    // abs(x - px)^2 + py^2 = D^2
    // abs(x - px)^2 = D^2 - py^2
    // x = px (+ or -) sqrt(D^2 - py^2)

    double px = points[idx].first, py = points[idx].second;
    double delta = sqrt(D * D - py * py);
    return seg(px - delta, px + delta);
}

int main() {
    int case_num = 0;
    while(scanf("%d%d", &N, &D)) {
        if(N == 0) break;

        case_num++;
        int ans = -1;
        double last = -1e9;
        bool ok = true;
        for(int i=0; i<N; i++) {
            double x, y;
            scanf("%lf%lf", &x, &y);

            // y 座標の絶対値が D を超えていれば無理
            if(abs(y) > D) ok = false;

            points[i] = make_pair(x, y);
        }
        if(!ok) goto end_prog;

        for(int i=0; i<N; i++) {
            segments[i] = calc_x(i);
        }
        sort(segments, segments + N);

        ans = 0;
        for(int i=0; i<N; i++) {
            if(last < segments[i].l) {
                last = segments[i].r;
                ans++;
            }
        }

    end_prog:
        printf("Case %d: %d\n", case_num, ans);
    }    
}

POJ 3190: Stall Reservations

問題リンク

閉区間が $N$ 個あり、 $i$ 番目の区間は $\left[ a_{i}, b_{i} \right]$ と表される。何回かの操作をしてこの区間を全て取りたい。 $1$ 回の操作では、overlap しない範囲でいくつでも区間を取ることができる (終点と始点の overlap も許されない。つまり取る区間それぞれについて $b_{p} \lt a_{q} (p \neq q, a_{p} \lt a_{q})$ を満たす)。このとき、操作の最小回数と、それぞれの区間について何回目の操作で取ったかを求めよ。

▶表示する

操作の最小回数を求めるだけなら imos 法で終わりですが、今回はそれぞれの区間について何回目の操作で取ったかも求める必要があるため、それだけでは答えられません。

まず、区間を (始点が小さい) → (終点が小さい) 順にソートし、区間を 1 つずつどこかの操作に割り当てることを考えます。

いままでの各操作で取った区間の中で、終点の最大値を覚えておくことにしましょう。始点が小さい順に割り当てているため、新たな区間をどこかの操作に割り当てるときは、終点の最大値が最も小さいものに割り当てるのが最適です。最小のものだけに興味があるため、priority_queue で管理することで少ない計算量で解くことができます。

struct Elem {
    int ub, idx;
    Elem() {}
    Elem(int a, int b) : ub(a), idx(b) {}
    bool operator<(const Elem &x) const {
        return ub > x.ub;
    }
};

struct seg {
    int l, r, idx;
    seg() {}
    seg(int a, int b, int c) : l(a), r(b), idx(c) {}
    bool operator<(const seg &x) const {
        if(l != x.l) return l < x.l;
        return r < x.r;
    }
};

int N;
seg segments[50010];
int ans[50010];

int main() {
    scanf("%d", &N);
    for(int i=0; i<N; i++) {
        int l, r; scanf("%d%d", &l, &r);
        segments[i] = seg(l, r, i);
    }
    sort(segments, segments + N);

    int last_idx = 0;
    priority_queue<Elem> que;
    for(int i=0; i<N; i++) {
        if(que.empty()) {
            // 最初は新しい操作割り当てするしかない
            que.push(Elem(segments[i].r, ++last_idx));
            ans[ segments[i].idx ] = last_idx;
        }
        else {
            Elem cur = que.top();
            // 既存の操作に割り当てられるのであれば割り当てる
            if(cur.ub < segments[i].l) {
                que.pop();
                que.push(Elem(segments[i].r, cur.idx));
                ans[ segments[i].idx ] = cur.idx;
            }
            else {
                que.push(Elem(segments[i].r, ++last_idx));
                ans[ segments[i].idx ] = last_idx;
            }
        }
    }

    printf("%d\n", last_idx);
    for(int i=0; i<N; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

その他

POJ 2393: Yogurt factory

問題リンク

ヨーグルト工場では、ヨーグルトの製造・配送・貯蔵を行っている。 $i$ 週目にヨーグルトを $1$ つ製造するには $C_{i}$ 円がかかり、またその週には $Y_{i}$ 個を配送しなければならないことがわかっている。ヨーグルトを $1$ 週間貯蔵するには $1$ つあたり $S$ 円がかかる。貯蔵に期限や個数の上限はない。 $N$ 週間の予定が与えられるので、配送の予定を全てクリアするときのコストの最小値を求めよ。

▶表示する

ヨーグルトはいくらでも貯蔵できるのですから、 $i$ 週目で発送するヨーグルトは $1$ 週目から $i$ 週目のどこかで作っていさえすればよいです。「 $i$ 週目のためのヨーグルトを作るタイミングが $i$ 個存在して、その中からなるべく安いタイミングで作る」と読み替えると、最も安いタイミングで貪欲に作れば良いことが分かります。

あとはどのようにして最小値を求めるかですが、普通にやると「今まで出てきたヨーグルトの価格全てに $S$ を足す (区間加算)」という操作や、「今まで出てきたヨーグルト価格の中で最小のものを求める (区間最小値)」のような操作が必要になります。遅延評価のセグメント木を使って解いても良いのですが、次のようにするとよりシンプルに解けます。

それぞれのヨーグルトについて、最後の週に価格がいくらになるかを求めて、今まで出てきた中での最小値を覚えておきます。今の週では、最後の週と比較していくら安くなっているかは簡単に分かるため、それを考慮しながら答えに加算すればよいです。

ll C[10010], Y[10010];
int main() {
    int N, S; scanf("%d%d", &N, &S);
    for(int i=0; i<N; i++) {
        scanf("%lld%lld", &C[i], &Y[i]);
    }

    ll ans = 0;
    ll mi = 1LL << 60;
    for(int i=0; i<N; i++) {
        // 最後の週における価格を出す
        // 今まで出てきたものよりも小さければ更新
        ll cur_val = C[i] + S * (N - 1 - i);
        mi = min(mi, cur_val);
        ans += (mi - S * (N - 1 - i)) * Y[i];
    }
    printf("%lld\n", ans);
    return 0;
}

POJ 1017: Packets

問題リンク

$1 \times 1, 2 \times 2, \dots, 6 \times 6$ の $6$ 種類の正方形がいくつかある。これらを全て、 $6 \times 6$ のいくつかの領域の中に重なりのないように敷き詰めたい。このとき、必要な $6 \times 6$ 領域の最小個数を求めよ。

▶表示する

大きいものから貪欲に入れていけばよいです。大きい物を入れると隙間ができるかと思いますが、その隙間にもなるべく大きなものを入れていくようにします。場合分けが非常に面倒ですが、ちゃんとやれば通ります。

int A[10];

// p 割る q の切り上げ (整数)
int ceil_int(int p, int q) {
    return (p + q - 1) / q;
}

// p から q を引く (結果が負になる場合は 0 に揃える)
void minus_nn(int &p, int q) {
    p -= min(p, q);
}

int main() {
    while(1) {
        int check_num = 0;
        for(int i=1; i<=6; i++) {
            scanf("%d", &A[i]);
            check_num |= A[i];
        }
        if(!check_num) break;

        int ans = 0, rest = 0;
        // 6 * 6 を入れる
        ans += A[6];

        // 5 * 5 を入れる (1 もできるだけ入れる)
        ans += A[5];
        minus_nn(A[1], A[5] * 11);

        // 4 * 4 を入れる (2, 1 もできるだけ入れる)
        ans += A[4];
        rest = max(0, A[4] * 5 - A[2]);
        minus_nn(A[2], A[4] * 5);
        minus_nn(A[1], rest * 4);

        // 3 * 3 を入れる (2, 1 もできるだけ入れる)
        ans += ceil_int(A[3], 4);
        A[3] %= 4;
        rest = (36 - A[3] * 9) % 36;
        if(rest) {
            // 2 * 2 は何個まで入れられるか
            int can_take_two = 2 * (4 - A[3]) - 1;

            // 実際に何個入れたか
            int actual_take_two = min(A[2], can_take_two);
            A[2] -= actual_take_two;
            rest -= actual_take_two * 4;

            // 1 を何個入れるか
            minus_nn(A[1], rest);
        }

        // 2 * 2 を入れる (1 もできるだけ入れる)
        ans += ceil_int(A[2], 9);
        A[2] %= 9;
        rest = (36 - A[2] * 4) % 36;
        A[1] -= min(A[1], rest);

        // 1 * 1 を入れる
        ans += ceil_int(A[1], 36);

        printf("%d\n", ans);
    }
    return 0;
}

POJ 3040: Allowance

問題リンク

あなたはコインを $N$ 種類持っている。具体的には、 $V_{i}$ 円のコインを $B_{i}$ 円持っている。コインの価格は小さい順に並べると倍数列 (すなわち、あるコインの価格はその次に価格が低いコインの倍数) である。手持ちから $C$ 円以上の金額を何回か払うことを考えるとき、払える回数の最大値を求めよ。

▶表示する

$C$ 円を超えるコインはそれ $1$ 枚で条件を満たしているため、明らかにその $1$ 枚だけを使って $1$ 回分払うのが良いです。以降、 $C$ 円未満のコインのみが存在すると仮定します。

倍数列になっているので、貪欲法で解くことはなんとなく察しが付きます。まずは $C$ 円を超えない程度に、金額の大きいものから貪欲に取っていくことにしましょう。それが終わったら、次は $C$ 円をギリギリ超過する程度に、金額の低いものから貪欲に取っていくことにしましょう。実は、この操作が最適解になります。

なぜこれでうまく行くのでしょうか？まずは、最初にやった「超えない程度に大きいものから取る貪欲」について考えてみましょう。金額が小さい他のコインをかき集めて大きい金額のコインと同額にすることはできますが、大きいコインの代わりに小さなコインで埋め合わせる戦略は、後でギリギリ超過させたいことを考えると、無駄であることが分かります。よって、超過しないのであれば大きいものから取るほうが良いです。

次に、「ギリギリ超過する程度に金額の低いものから取る貪欲」について考えてみましょう。これは先ほどの逆を考えればよいです。金額の低いものを高いものに置き換えてこの貪欲をした場合を考えると、あとあとになって金額の低いものしか残らず、無駄が発生します。よって、小さいものから取るほうが良いです。

説明になっているかどうかはわかりませんが、これで解けます (難しいですね・・・)

int N; ll C;
pair<ll, ll> coins[25];
ll use[25];

int main() {
    scanf("%d%lld", &N, &C);

    for(int i=0; i<N; i++) {
        ll value, num;
        scanf("%lld%lld", &value, &num);
        coins[i] = make_pair(value, num);
    }
    sort(coins, coins + N, greater< pair<ll, ll> >());

    ll ans = 0; int idx = 0;

    // C 円以上の硬貨であれば 1 枚だけ渡すのが最適
    while(coins[idx].first >= C && idx < N) {
        ans += coins[idx++].second;
    }

    while(1) {
        memset(use, 0LL, sizeof(use));
        int cur = idx; ll sum = 0;

        // 価値の高いものから、超過しない範囲で貪欲
        while(cur < N && sum < C) {
            // 入れて良い金額と、入れて良い枚数
            ll rest = C - sum;
            ll num = min(coins[cur].second, rest / coins[cur].first);
            sum += num * coins[cur].first;
            use[cur++] += num;
        }

        // 価値の小さいものから、ギリギリ超過するように貪欲
        cur = N - 1;
        while(cur >= idx && sum < C) {
            ll rest = C - sum;
            ll num = min(coins[cur].second - use[cur], (rest + coins[cur].first - 1) / coins[cur].first);
            sum += num * coins[cur].first;
            use[cur--] += num;
        }

        if(sum < C) break;
        ll add = 1LL << 60;
        for(int i=idx; i<N; i++) {
            if(use[i]) add = min(add, coins[i].second / use[i]);
        }

        ans += add;
        for(int i=idx; i<N; i++) {
            if(use[i]) coins[i].second -= use[i] * add;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

POJ 1862: Stripies

問題リンク

$N$ 匹の生き物がおり、 $i$ 番目の生き物の体重は $w_{i}$ である。体重が $w_{i}, w_{j}$ である $2$ 匹の生き物同士がぶつかると、元いた生き物は消え、新たに体重 $2 \times \sqrt{w_{i} w_{j}}$ の生き物が $1$ 匹現れる。生き物がぶつかって最終的に $1$ 匹だけになるとき、最後に残った生き物の体重の最小値を求めよ。

▶表示する

最小化を考えているため、大きい数字はたくさんルートがかかったほうが良いです。したがって、大きいものから貪欲にぶつけるだけです。

int A[110];
int main() {
    int N; scanf("%d", &N);
    for(int i=0; i<N; i++) {
        scanf("%d", &A[i]);
    }
    sort(A, A+N, greater<int>());

    double ans = A[0];
    for(int i=1; i<N; i++) {
        ans = 2 * sqrt(ans * A[i]);
    }
    printf("%.3f\n", ans);
    return 0;
}

POJ 3262: Protecting the Flowers

問題リンク

牛が $N$ 頭おり、 $i$ 番目の牛は座標 $T_{i} (\gt 0)$ におり、単位時間あたり $D_{i}$ だけ花を食べている。牛を $1$ 頭ずつ納屋に帰すことを考える。納屋は座標 $0$ にあるため、帰すには (納屋から牛のところまで行く) + (牛のところから納屋に帰る) で $2T$ かかり、帰す対象の牛は待っている間も、帰っている間も花を食べない。このとき、全ての牛が納屋に帰るまでに食べられる花の量の合計を最小化せよ。

▶表示する

ある $2$ 頭の牛 $i, j$ について、 $i \rightarrow j$ の順番で帰すか、 $j \rightarrow i$ の順番で帰すかによって、この $2$ 頭による損失がどう変わるのかを考えてみましょう。

$i \rightarrow j$ の順番で帰す ... 損失は $2 \times T_{i} \times D_{j}$
$j \rightarrow i$ の順番で帰す ... 損失は $2 \times T_{j} \times D_{i}$

損失を最小化したいのですから、 $T, D$ をソート時にキーとして使うことで、最適なものがわかります。

struct Elem {
    ll dist, cost;
    // 損失が最小になるようにソートする
    bool operator<(const Elem &x) const {
        return dist * x.cost < x.dist * cost;
    }
};

ll N;
Elem A[100010];

int main() {
    scanf("%lld", &N);
    for(int i=0; i<N; i++) {
        scanf("%lld%lld", &A[i].dist, &A[i].cost);
    }

    ll acc = 0, ans = 0;
    sort(A, A+N);

    for(int i=0; i<N; i++) {
        ans += acc * A[i].cost;
        acc += 2 * A[i].dist;
    }

    printf("%lld\n", ans);
    return 0;
}

次回は動的計画法を解説します！

hogecoder

tsutaj 競技プログラミングの記録

蟻本練習問題解説 Part2 (2-2)

猪突猛進！ "貪欲法"

区間

POJ 2376: Cleaning Shifts

POJ 1328: Radar Installation

POJ 3190: Stall Reservations

その他

POJ 2393: Yogurt factory

POJ 1017: Packets

POJ 3040: Allowance

POJ 1862: Stripies

POJ 3262: Protecting the Flowers