ABC104 C - All Green

久しぶりに問題を解いていたら、C問の中でも個人的に骨が折れた問題があったのでメモ
ボーナス点という要素がなければ欲張り法で解ける問題ですが、これの所為で他の解説者の方の言う通り、2ⁿの全解探索が必要です。
最高で1024通りを試しますが、対象の問題のビットが立っている時、問題数*問題点+ボーナス点を加算し、目標点数Gに届いていなければ、欲張り法で残りの必要点数を加算していきます。
最下位ビットが立っているときは、2で割る時余りが1になるので、ビットはループ回数の2の剰余で求めます。
ビットのたった問題は全て解いたと仮定するので、vectorでチェックしていて、問題が全て解かれているものを除き、点数の高い問題から残りの必要点数を加算していきます。
この時、1つの問題に就き問題数全てを加算すると、上記の前提が外れるので最高でも問題点*(問題数-1)しか加算しません。
単なる2ⁿの探索のみならず、様々な要素が組み合わさっているので個人的には難しかったです。

#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 点) - けんちょんの競プロ精進記録

ABC104 参加記録 - ARMERIA