AtCoder Beginner Contest 104 - C - All Green
むずい...これが300問題...?
https://gyazo.com/17617621e55fa134a18a5c7f1fb4f623
解説を見て
考えてもさっぱりわからなかったので解説を見た
基本的には得点が多い問題をなるべく狙った方がいい
ボーナス点があることを考えて、ボーナスを狙って低い得点問題を解いた方がいいときもある
dがたかだか10しかないので、bit全探索を行ってどのボーナスを狙うか全て調べてみても間に合う
$ 2^{10} = 1024 = 10^3
bit全探索でbitが立っているところを全完する問題と決め打ちする
これだけだとダメで、その全完した得点が目標に届いていない場合は、まだ解いていない問題から一番点が高いのを選んで、その問題で目標点を超えれるかをみる
提出したコード
code: C.cpp
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
int main() {
ll d,g; cin >> d >> g;
vector<ll> p(d);
vector<ll> c(d);
rep(i, d) {
}
ll ans = LONG_MAX;
// 全完する得点の問題を決めてbit全探索
for (int bit = 0; bit <= (1<<d); bit++) {
// 合計点
ll sum = 0;
// 解いた問題数
ll count = 0;
rep(i, d) {
if(bit & (1<<i)) {
sum += ci + pi * 100 * (i+1); }
}
// 既に目標点を超えてる場合
if(sum >= g) chmin(ans, count);
else {
// 超えていない場合は、残っている問題の中で一番配点が高いのを解く
// デクリメントするforで配点が大きい順に見ていく
for(int i=d-1; i >= 0; i--) {
// 既に全完している問題は飛ばす
if(bit & (1<<i)) continue;
if(sum >= g) break;
sum += 100 * (i+1);
count++;
}
// 中途半端に解くのは1つだけなのでbreakする
break;
}
// 超えていればcountを更新
if(sum >= g) chmin(ans, count);
}
}
cout << ans << endl;
return 0;
}