頭良くなりたい人

文系大学生shadeのブログです。競技プログラミングや人文学の話題,受験ネタなど。

ABC167 C - Skill Up

問題はこちら atcoder.jp

方針

購入する参考書の組み合わせが高々 2^{12} 通りしかないところを見るに,全探索で解くのが本命です。

今回は「bit全探索」を用いていますが,この手法を使った経験がなかったのでたどたどしいコードになっています。

コード

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)

int n,m,x;
vector<int> c;
vector<vector<int>> a;

bool judge(int bit);
int cost(int bit);

int main(){
    cin>>n>>m>>x;
    c.resize(n);
    a.resize(n);
    REP(i,n){
        cin>>c[i];
        a[i].resize(m);
        REP(j,m){
            cin>>a[i][j];
        }
    }
    int min_=0;

    // 参考書の組み合わせ分(2^12回)のループ
    for(int bit=0; bit<(1<<n); bit++){
        if(judge(bit)){
            if(min_==0){
                min_=cost(bit);
            }else{
                min_=min(min_,cost(bit));
            }    
        }
    }           
    
    cout<<(min_==0 ? -1 : min_)<<endl;
}

bool judge(int bit){
    vector<int> und(n); // 理解度

    REP(i,n){
        if(bit&(1<<i)){
            REP(j,m){
                und[j]+=a[i][j];
            }
        }
    }

    REP(i,m){
        if(und[i]<x){
            // 理解度がXに達していない問題があればfalse
            return false;
        }
    }

    return true;
}

int cost(int bit){
    int sum=0;
    REP(i,n){
        if(bit&(1<<i)){
            sum+=c[i];
        }
    }

    return sum;
}