[AtCoder] ABC 104 C – All Green

2020年12月12日

問題

方針

問題を解く順番は関係ないので、コンプリートする問題を全探索します。これは、ビット全探索で解くことはできます。コンプリートした問題の集合を \( 2 \) 進数で表し、点数が \( G \) 未満ならば、コンプリートしていない問題の中で一番点数の高い問題を解き、\( G \) 以上になるかを確かめます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int D, G;
    cin >> D >> G;
    int p[D], c[G];
    for (int i = 0; i < D; i++) {
        cin >> p[i] >> c[i];
    }
    int n = 1<<D;
    int best = INT32_MAX;
    for (int i = 0; i < n; i++) {
        int t = 0;
        int s = 0;
        for (int j = 0; j < D; j++) {
            if ((i & (1<<j))) {
                t += p[j];
                s += (j + 1) * 100 * p[j]+ c[j];
            }
        }
        for (int j = D - 1; j >= 0; j--) {
            if ((i & (1<<j)) == 0 && s < G) {
                if ((G - s) / 100 <= p[j] * (j + 1)) {
                    t += max(1, (G - s) / 100 / (j + 1));
                    s = G;
                }
                break;
            }
        }
        if (best > t && s >= G) {
            best = t;
        }
    }
    cout << best << "\n";
    return 0;
}