全探索の使い方の復習

##前回
[再帰処理を学ぶ](https://qiita.com/RubyLrving/items/456fb9bb72dee9b63cf9)からの続きです。
たくさんの数式の後から解いていきます。

##[ABC 079 C - Train Ticket](https://atcoder.jp/contests/abc079/tasks/abc079_c)
過去に解いてます。

- bit全探索を使いました。

##[C - All Green](https://atcoder.jp/contests/abc104/tasks/abc104_c)
問題文はAtCoderを参照してください。

- 単純に考えると高難易度の問題から解く。
- 例外は全問解いた際のボーナスポイント。
- ボーナスポイントが入る条件をbit全探索する。
- 10!は3628800、それに加えて10×100＝1000を足す。余裕で間に合います。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    int d;
    ll g;
    cin >> d >> g;
    vector<int> p(d, 0);
    vector<int> c(d, 0);
    
    for(int i=0; i<d; i++){
        cin >> p[i] >> c[i];
    }
    
    int ans=1000;
    for(int bit=0; bit<(1 << d); bit++){
        int question=0;
        int order=0;
        ll score=0;
        while(order<d){
            if((bit>>order)&1){
                score += p[order] * 100 * (order+1) + c[order];
                question += p[order];
            }
            order++;
        }
        
        if(score>=g){
            ans =  min(ans, question);
            continue;
        }
        
        order=d-1;
        int count=0;
        while(order>=0){
            if(!(bit>>order&1)){
                score += (order+1)*100;
                question++;
                if(score>=g){
                    ans =  min(ans, question);
                    break;
                }
            }
            count++;
            if(p[order]<count){
                order--;
                count=0;
            }
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

```

##[A - 高橋君とお肉](https://atcoder.jp/contests/arc029/tasks/arc029_1)
問題文はAtCoderを参照してください。

- bit全探索にて、0なら1台目、1なら２台目で肉を焼くとする
- 最大200秒、2^4の為処理速度は考慮しない

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    
    vector<int> t (n, 0);
    for(int i=0; i<n; i++){
        cin >> t[i];
    }
    
    int time=200;
    for(int bit=0; bit<(1<<n); bit++){
        int t1=0;
        int t2=0;
        for(int i=0; i<n; i++){
            if(bit>>i&1){
                t2+=t[i];
            }else{
                t1+=t[i];
            }
        }
        
        time = min(time, max(t1, t2));
    }
    
    cout << time << endl;
    
    return 0;
}
```

ここまで勉強してきたなら凄く簡単な問題です。
何も見ずにACとして通せます。

##[D - 派閥](https://atcoder.jp/contests/abc002/tasks/abc002_4)
問題文はAtCoderを参照してください。

- 無向グラフと呼ばれるデータ構造を使おうと思いました。
- しかし、そこから何をしていいか分からず全探索をしました。
- 計算量はO(N^3)、12^3=1728

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    
    int n, m;
    cin >> n >> m;
    
    bool graph[12][12] = {false};
    for(int i=0; i<m; i++){
        int x, y;
        cin >> x >> y;
        graph[x-1][y-1] = true;
        graph[y-1][x-1] = true;
    }

    int ans=0;
    for(int bit=0; bit<(1<<n); bit++){
        bool f=true;
        int c=0;
        for(int i=0; i<n; i++){
            if(bit>>i&1){
                c++;
                for(int j=i+1; j<n; j++){
                    if(bit>>j&1){
                        if(!graph[i][j]){
                            f=false;
                        }
                    }
                }
            }
        }
        if(f) ans = max(ans, c);
    }
    
    cout << ans << endl;
    
    return 0;
}
```