蟻本の練習問題埋め2-2(2) - 競技プログラミング+αなブログ

貪欲法（その他）
ちょっとしんどくなってきた

POJ 2393 - Yogurt factory

問題

N週間後までのヨーグルトの製造計画を立てる。
i週目にヨーグルトを1単位製造するのにCiセントかかる。
ヨーグルトは貯蔵庫に保存でき、1単位のヨーグルトを1週間保存するのにSセントかかる。
i週目にはYi単位のヨーグルトの需要がある。
全ての週で需要に答えるときコストの最小値はいくらか。

制約

N<=10000
Ci<=5000
S<=100
Yi<=10000

解法

いま、i週目の需要に答えることを考える。
j(<=i)週目にヨーグルトを製造し、それを貯蔵しておいたとき、1単位あたりにかかるコストAjは
Aj = Ci + S*(i-j)
である。
このとき、1単位あたりのコストがmin{Aj}となるような製造方法で需要に答えるのが最善となる。
Ajをiに関する1次関数と見ると、1次の係数は全て等しい。
よってiが変わってもAjの大小関係は変わらないので、最小のAjだけを保持しておけばいいことになる。
これによりO(N)で解ける。

POJ 1017 - Packet

http://poj.org/problem?id=1017

問題

6*6の正方形領域をいくつか用意し、1*1~6*6の正方形を詰め込む。
1*1~6*6の正方形を詰め込む個数がそれぞれ与えられるので、6*6の正方形領域が最低何個必要かを求めよ。

制約

特になし

解法

大きい順に詰め込んでいく。
大きい順に詰め込むとき、1*1と2*2を最大いくつ隙間に入れることが出来るかを記録しておく。
3*3の場合は、4で割った余りによって、1*1と2*2を隙間に入れることが出来る個数が変わる。

POJ 3040 - Allowance

http://poj.org/problem?id=3040

問題

N種類のコインがある。
それぞれのコインの価値は次に大きいコインの価値を割り切る。
それぞれのコインの枚数が与えられるので、そこからC以上の値段を払うことは最大で何回可能か。

制約

N<=20
C<=10^9
コインiの価値<=10^9
コインiの枚数<=10^6

解法

まず、1枚でC以上の価値を持つものは、1枚で払う。
基本的に価値が大きい順に払うが、超過する場合に無駄をしている可能性がある。
そこで、超過する一歩手前で止め、残っているコインのうち一番価値が小さいものを使ってC以上にする。
貪欲法は何故それで大丈夫なのかという説明が難しい…
強いて言えば、「それぞれのコインの価値は次に大きいコインの価値を割り切る」という制約より、価値が大きいコインから超過しないように払っていったとき、無駄な払い方をするようなことはないから。
すなわち、より価値が小さいコインを先に払ったとしても、せいぜい同じ金額に辿り着くのみ。
それなら出来るだけ、超過の時に無駄が少ない価値が小さなコインを残しておくべき、という考え。

ソース

int main() {
  int n, c;
  scanf("%d %d", &n, &c);
  ll ans = 0;
  vector<pii> v;
  REP(k,n) {
    int a, b;
    scanf("%d %d", &a, &b);
    if (a >= c) {
      // 1枚で超えるものはそれだけで払う
      ans += b;
    } else {
      v.push_back(pii(a,b));
    }
  }
  n = v.size();
  sort(ALL(v), greater<pii>());
  while(1) {
    vector<int> use(n,0);
    ll now = 0;
    // 大きいものからcを超えないように出来るだけ払う
    REP(i,n) {
      for (int j=0; j<v[i].second; ++j) {
        if (now + v[i].first > c) {
          break;
        }
        now += v[i].first;
        use[i]++;
      }
    }
    if (now < c) {
      // cに達していない場合、まだ残っている一番小さいもので払う
      // 超過しないように出来るだけ使っているはずなので、１枚付け足すだけで良い
      for (int i=n-1;i>=0;--i) {
        if (v[i].second-use[i]>0) {
          now += v[i].first;
          use[i]++;
          break;
        }
      }
    }
    if (now < c) break;         // 払えなかった
    // 同じ払い方を出来る限り繰り返す
    int a = INF;    // 同じ払い方が出来る最大回数
    REP(i,n) if (use[i]) a = min(a, v[i].second/use[i]);
    REP(i,n) v[i].second -= use[i]*a;
    ans += a;
  }
  cout << ans << endl;
}

POJ 1862 - Stripies

http://poj.org/problem?id=1862

問題

重さw[i]の生物がn匹いる。
重さaとbである２匹の生物が合体すると、重さは2*sqrt(a*b)となる。
最後に残る生物の重さの最小値を求めよ。

制約

n<=100
w[i]<=10000

解法

初めに合体するほどルートが沢山つくので、大きい順に合体させる。
大きいのは合体の度に調べれば良い。

POJ 3262 - Protecting the Flowers

http://poj.org/problem?id=3262

問題

N匹の牛が花を食べている。全て牛を小屋に戻すことにより、花の被害を最小限にしたい。
i番目の牛を小屋に戻すのには2*T[i]かかり、i番目の牛は１分にD[i]の花を食べる。
牛は１匹ずつしか小屋に戻すことはできない。
また、牛は小屋に戻され始めるまで花を食べ続ける。
最善の戻し方をしたとき、牛に食べられる花の最小値を求めよ。

制約

N<=10000
T[i]<=2000000
D[i]<=100

解法

牛aと牛bを比べたとき、どちらを先に小屋に戻すべきかを考える。
牛aと牛b以外の牛のD[i]の合計をSとするとき、食べられる花の量は

牛iを先に小屋に戻す場合

　2*T[a] * (S + D[b]) + 2*T[b]*S --- (1)

牛jを先に小屋に戻す場合

　2*T[b] * (S + D[a]) + 2*T[a]*S --- (2)
となる。
(1)<(2)すなわち、T[a]*D[b]