久しぶりに問題を解いていたら、C問の中でも個人的に骨が折れた問題があったのでメモ
ボーナス点という要素がなければ欲張り法で解ける問題ですが、これの所為で他の解説者の方の言う通り、2nの全解探索が必要です。
最高で1024通りを試しますが、対象の問題のビットが立っている時、問題数*問題点+ボーナス点
を加算し、目標点数G
に届いていなければ、欲張り法で残りの必要点数を加算していきます。
最下位ビットが立っているときは、2で割る時余りが1になるので、ビットはループ回数の2の剰余で求めます。
ビットのたった問題は全て解いたと仮定するので、vector
でチェックしていて、問題が全て解かれているものを除き、点数の高い問題から残りの必要点数を加算していきます。
この時、1つの問題に就き問題数全てを加算すると、上記の前提が外れるので最高でも問題点*(問題数-1)
しか加算しません。
単なる2nの探索のみならず、様々な要素が組み合わさっているので個人的には難しかったです。
#include<iostream> #include<vector> #include<cmath> using namespace std; int main(){ int d,g; cin >> d >> g; vector<int> p(d),c(d); for(int i = 0; i < d; i++) cin >> p[i] >> c[i]; int loop = pow(2,d); int min = 10000; for(int i = 0; i <= loop-1; i++){ int t = i,tg = g; vector<int> check(d,0); int j=0,count=0; while(t != 0){ if(t%2 == 1){ tg -= p[j]*(j+1)*100+c[j]; count += p[j]; check[j] = 1; } t /= 2; j++; } for(j = d-1; j >= 0; j--){ if(tg <= 0) break; if(check[j] == 0){ for(int k = 0; k < p[j]-1 && tg > 0; k++){ tg -= (j+1)*100; count++; } } } if(count < min && tg <= 0) min = count; } cout << min; }
参考:
AtCoder Beginner Contest 104 C - All Green (300 点) - けんちょんの競プロ精進記録