C - All Green

コメント歓迎です。
今回もビット全探索を使います。

問題

AtCoder 版！蟻本 (初級編) - Qiita より

beta.atcoder.jp

方針

この問題では、同じ得点の問題を全問解くとボーナス点が貰えるところがポイントになります。
合計点が目標値以上になる最小の解答数を求め、出力します。

ビット全探索を使い、「どの得点のボーナスをもらうか」を全探索します。
もちろん、ボーナスを1つももらわない場合が最小回答数になる場合もあります。

その場合は、ビット列のうち"1"がボーナスをもらう得点と定義すると、オールゼロで表現できます。

また、ボーナスをもらっても目標値に届かないことが予想できます。
その場合は他の問題を追加で解く必要がありますが、
解く問題は1問あたりの得点が一番高いものを解くのが最適解になります。

そのため、1問あたりの得点が1番高いもの以外を追加で解くことについては考える必要がありません。

追加で解く問題数を計算する式は、割り算の切り上げをしています。
便利なテクニックだと思いますので、見たことがなければ実際に数字を当てはめて考えてみてください。

コード(AC)

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

int main(){
  // 入力
  int D, G;
  cin >> D >> G;

  vector<int> p(D, 0);
  vector<int> c(D, 0);

  for (int i = 0; i < D; i++) {
    cin >> p[i];
    cin >> c[i];
  }

  int ans = 1001; // 問題数は最大10 * 100

  // ビット全探索　2^D
  // ある配点の問題を全問解く
  // 全問解く配点をビット探索　"1":その配点の問題を全問解く
  for (int mask = 0; mask < (1 << D); mask++) {
    int sum = 0;
    int solve_count = 0; // 解いた問題数
    int rest_max = -1;   // 解かない問題で最も配点が高い問題
    for (int i = 0; i < D; i++) {
      if (mask >> i & 1) {
        sum += 100 * (i + 1) * p[i] + c[i]; // 全問解答＋ボーナスの点数
        solve_count += p[i];
      }
      else {
        rest_max = i; // 解かない問題で最も配点が高い問題を保持
      }
    }
    // 合計値が目標値以下の場合
    if (sum < G) {
      int tmp = 100 * (rest_max + 1); // 追加解答する問題の配点
      int shortage = (G - sum + tmp -1) / tmp; // 追加解答する問題数(不足分)
      // 不足分がその配点の問題数以下なら処理を継続
      if (shortage >= p[rest_max]) {
        continue;
      }
      solve_count += shortage; // 解答した問題数を更新
    }
    ans = min(ans, solve_count); // 解答数が過去最小なら更新
  }

  // 出力
  cout << ans << endl;
}