すごく教育的な「bit 全探索 + Greedy」！！！

問題概要

100 点問題, 200 点問題, 300 点問題, ..., 100× $D$ 点問題がそれぞれ $p_1, p_2, \dots, p_D$ 問ずつある。

今、精進して合計で $G$ 点以上獲得したい。ただし、100× $i$ 点問題を $p_i$ 問すべて解いた場合にはボーナスとして $c_i$ 点加算される。

最小の solve 数で $G$ 点以上獲得せよ。

制約

$1 \le D \le 10$

考えたこと

直感的には高得点から解いて行けば行くほど $G$ 点に到達するのが早く思えるが、ボーナスポイントという概念が存在するため、もし低得点帯でもボーナスがメチャクチャ美味しかったらその限りではなくなる...

これはなんか結構大変な Greedy になりそうな予感がするところに、制約 $D \le 10$ が目に入る。ごく自然に

全完する難易度帯を $2^{D}$ 通り決め打ちする

という解法が浮かぶ。これを決め打ちしてしまえば、

それだけで $G$ 点に到達する場合はそれで OK
それだけでは到達しない場合は、全完対象でないもののうち Greedy に高難易度から順に解いて行けば OK

ここで全完対象でないものを結果的に全完してしまう場合などへの不安が頭をよぎるが、そういうやつは「そういうやつについても全完するように決め打ちした場合」できちんと考慮されるはずなので気にしなくて OK！

#include <iostream>
#include <vector>
using namespace std;

int D;
long long G;
vector<long long> p, c;

int main() {
  cin >> D >> G;
  p.resize(D); c.resize(D);
  for (int i = 0; i < D; ++i) cin >> p[i] >> c[i];

  long long res = 1<<29;
  for (int bit = 0; bit < (1<<D); ++bit) {
    long long sum = 0;
    long long num = 0;
    for (int i = 0; i < D; ++i) {
      if (bit & (1<<i)) sum += c[i] + p[i] * 100 * (i+1), num += p[i];
    }
    if (sum >= G) res = min(res, num);
    else {
      for (int i = D-1; i >= 0; --i) {
        if (bit & (1<<i)) continue;
        for (int j = 0; j < p[i]; ++j) {
          if (sum >= G) break;
          sum += 100 * (i+1);
          ++num;
        }
      }
      res = min(res, num);
    }
  }
  cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 104 C - All Green (2Q, 水色, 300 点)

問題概要

制約

考えたこと