貪欲法…その他（5題）
プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～
この本の章末で紹介されている練習問題を解いている。貪欲法（その他）だ。
貪欲法とはいっても、この問題群は要素を選ぶ順番をうまく決めてソートするだけのものもあった。箱詰めとか硬貨の支払いは貪欲っぽさがあるが、ストライピーの合体は大きい順に合体させるだけだった。
POJ1017: Packets
問題概要
6種類の箱がある。箱の縦横はそれぞれ1*1,2*2,3*3,4*4,5*5,6*6となっている。
これらの箱を入れる容器は縦横が6*6で、容器に箱をつめていく。
入力としてそれぞれの箱の個数が与えられるので、箱をすべて詰めるのに最小でいくつの容器が必要かを求める。
解法
貪欲。大きな箱から詰めていく。隙間ができたら、隙間に入る大きな箱から詰めていく。
#include <iostream> #include <cmath> #include <vector> #include <queue> #include <utility> #include <algorithm> using namespace std; int main() { int p[6]; while (1) { // 入力 cin >> p[0] >> p[1] >> p[2] >> p[3] >> p[4] >> p[5]; if (!(p[0] | p[1] | p[2] | p[3] | p[4] | p[5])) break; int cnt = 0; // 計算 // 6*6 cnt += p[5]; // 5*5 cnt += p[4]; p[0] = max(p[0] - 11 * p[4], 0); // 4*4 cnt += p[3]; int i = max(5 * p[3] - p[1], 0); p[1] = max(p[1] - 5 * p[3], 0); p[0] = max(p[0] - 4 * i, 0); // 3*3 cnt += (p[2] + 3) / 4; // 4で割って切り上げ i = p[2] % 4; if (i != 0) { int n = 7 - 2 * i; // 5 3 1 while (n > 0) { if (p[1] > 0) { p[1]--; } else { p[0] = max(p[0] - 4, 0); } n--; } p[0] = max(p[0] - (8 - i), 0); } // 2*2 cnt += (p[1] + 8) / 9; // 9で割って切り上げ if (p[1] % 9 != 0) p[0] = max(p[0] - 4 * (9 - p[1] % 9), 0); // 1*1 cnt += (p[0] + 35) / 36; // 36で割って切り上げ // 出力 cout << cnt << endl; } }
POJ1862: Stripies
問題概要
ストライピーと呼ばれるアメーバのような生物が群生している。
ストライピーは2匹が衝突すると合体する。
2匹のストライピーの重さをm1, m2とすると、合体したストライピーの重さは2*sqrt(m1*m2)である。
ストライピーの群れが合体を繰り返して最終的に1匹になった時に合計の重さの最小値を求めよ。
1 <= n <= 100
1 <= w <= 10000
解法
重さの大きい順に合体させる。
なぜそれでうまくいくかを説明する。重さがa,b,cの3匹をa->b->cの順に合体させると、
重さは2*sqrt(c, 2 * sqrt( b, a))となる。見やすくするために2を消して4乗すると、
c^2 * b * a となる。
よって、あとから合体させたcは他の二つにくらべて合体体重への寄与が大きく、3体なら重さの小さいものをあとから合体させたほうが合体体重が小さくなることが分かる。一般的にn体の合体を考えても、重さの大きい順に合体させれば良い。
#include <iostream> #include <cmath> #include <vector> #include <utility> #include <algorithm> using namespace std; int main() { // 入力 int n; cin >> n; vector<int> w(n); for (int i = 0; i < n; i++) { cin >> w[i]; } sort(w.begin(), w.end()); // 計算 // 重さの大きい順に合体させる。 double res = *w.rbegin(); for (int i = w.size() - 2; i >= 0; i--) { res = 2 * sqrt(res * w[i]); } // 出力 printf("%.3f\n", res); }
POJ2393: Yogurt factory
問題概要
ヨーグルトをN週間にわたって出荷する。各週にヨーグルトを生産するコストは変動し、週iにヨーグルトを1ユニット生産するコストはCiである。ヨーグルトはいくらでも生産でき、あまった分は保管できる。保管するのにかかるコストは、1ユニット1週間あたりSである。週iに出荷すべきヨーグルトの量はYiで与えられる。ヨーグルトを出荷するのにかかる生産・保管コストの和の最小値を求めよ。
1 <= N <= 10000
1 <= Ci <= 5000
1 <= S <= 100
1 <= Yi <= 10000
解法
週iのヨーグルトを生産する最小コストは、週i-1の最小コスト+保管コストSと、週iの生産コストとのうち小さいほうである。
あとは週1から順に計算すればO(N)。
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { // 入力 int n, s; cin >> n >> s; vector<int> c(n); vector<int> y(n); for (int i = 0; i < n; i++) { cin >> c[i] >> y[i]; } // 計算 int i = 0; // 現在の最小コスト int min_y = 10000; int cost; long long total = 0; // 先週までの最小コストの週を保管した場合と今週のコストを比較して、最小コストを更新する do { // 最小コストの更新 min_y = min(c[i], min_y + s); total += y[i] * min_y; } while (++i < n); // 出力 cout << total << endl; }
POJ3040: Allowance
問題概要
硬貨の支払い問題。N種類の硬貨があり、それぞれの硬貨の金額は次の大きさの硬貨の金額を割り切るようになっている。
硬貨iの金額Viと、その硬貨をBi枚持っているという情報が与えられ、硬貨を使ってベッシーに金額C以上の給料を毎週支払いたい。
最大で何週間給料を支払うことができるか。
1 <= N <= 20
1 <= Vi <= 100,000,000
1 <= Bi <= 1,000,000
1 <= C <= 100,000,000
解法
大きな硬貨から支払う。まず1枚の硬貨でC以上の金額になるものは1枚で支払う。そうでない硬貨については、金額がCを超えないように大きな硬貨から埋めていき、いちばん小さな硬貨まで埋める。そして金額がCに達していなければ、残っている硬貨のうち金額の最も小さな硬貨を1枚加える。そうすると金額がC以上になる。これでうまくいく理由は、金額Cを超過する量について最も無駄が少ない支払い方だからである。
#include <iostream> #include <cmath> #include <vector> #include <queue> #include <utility> #include <algorithm> using namespace std; const int INF = 1000000000; int main() { // 入力 int n, c, v, b; long long res = 0; vector< pair<int, int> > vb; cin >> n >> c; for (int i = 0; i < n; i++) { cin >> v >> b; // 硬貨1枚で金額c以上になるものは先に支払う if (c <= v) { res += b; } else { vb.push_back(make_pair(v, b)); } } sort(vb.begin(), vb.end()); // 計算 // lot: 1回の支払いで使うそれぞれの硬貨の枚数 int m = vb.size(); vector<int> lot(m); while (1) { int current = c; // 金額の高い硬貨から合計金額cを超えないように埋めていく for (int i = m -1; i >= 0; i--) { lot[i] = min(current / vb[i].first, vb[i].second); current -= lot[i] * vb[i].first; vb[i].second -= lot[i]; } // 不足金額があり、かつ支払い可能であるなら、残っている硬貨のうち最も金額の小さい硬貨1枚で支払うことができる if (current > 0) { for (int i = 0; i < m; i++) { if (vb[i].second > 0) { vb[i].second--; lot[i]++; current -= vb[i].first; break; } } } // まだ支払い金額が残っているなら支払い不可能 if (current > 0) break; res++; // lotの硬貨の組み合わせで支払える回数だけ支払う int num = INF; for (int i = 0; i < m; i++) { if (lot[i] > 0) num = min(vb[i].second / lot[i], num); } res += num; for (int i = 0; i < m; i++) { vb[i].second -= num * lot[i]; } } // 出力 cout << res << endl; }
POJ3262:
3262 -- Protecting the Flowers
問題概要
ジョンはN頭の牛を放牧している。ジョンが戻ったとき、牛たちが庭に入って花を食べていた。花の被害を最小にするため、ジョンはすぐに牛を小屋に戻すことにした。
牛iは小屋からTi分の場所にいる。移動を待っている間、1分当たりDiの花を食べる。ジョンは一度に1頭の牛しか移動させられない。牛iを移動させ終えるのに2*Ti分かかる。ある牛を移動させてから別の牛を移動させるまでに余分の時間はかからない。花の被害が最小に食い止められるように牛を順番に移動させるプログラムをかけ。
2 <= N <= 100000
1 <= Ti <= 2000000
1 <= Di <= 100
解法
牛aの移動時間t[i]、花の破壊量d[i]とし、
牛bの移動時間t[j]、花の破壊量d[j]とする。牛aと牛bではどちらを先に移動させるべきかを考えよう。
牛aとb以外の牛たちの花の破壊量の話をSとすると、
a -> bの順で牛を移動させたときの花の被害は、
f_a = t[i] * (S + d[j]) + t[j] * S
であり、
b -> aの順で牛を移動させたときの花の被害は、
f_b = t[j] * (S + d[i]) + t[i] * S
である。
これらの差をとると、
f_a - f_b = t[i] * d[j] - t[j] * d[i]
この値が正ならa->bのほうが破壊量が大きいのでb->aを選ぶべきである。
この値によって比較してソートすれば移動させるべき牛の順番がわかる。
#include <iostream> #include <cmath> #include <vector> #include <queue> #include <utility> #include <algorithm> using namespace std; struct Cow { int d,t; // この比較がキモである bool operator<(const Cow& another) const { return t * another.d < d * another.t; } }; int main() { // 入力 int n; cin >> n; vector<Cow> cows(n); int t,d; long long dsum = 0; for (int i = 0; i < n; i++) { scanf("%d%d", &t, &d); cows[i].t = 2 * t; cows[i].d = d; dsum += d; } // 貪欲法のためのソート sort(cows.begin(), cows.end()); // 貪欲 long long res = 0; for (int i = 0; i < n; i++) { dsum -= cows[i].d; res += dsum * cows[i].t; } cout << res << endl; }
