全探索：全列挙, 工夫して通り数を減らす全列挙, ビット全探索

#[レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】](https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7%B4%9A%E8%80%85%E3%81%8C%E8%A7%A3%E3%81%8F%E3%81%B9%E3%81%8D%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-100-%E5%95%8F)

初級編を解いて茶色パフォーマンス（７５０）を出しても茶色に上がれませんでした。
昔とレベルが変わってきたのでしょう。
初級編が終わったので次のステップへ進みます。
ただし、下記問題は全部は解きません。
なぜなら情報オリンピックの問題とか分からないからです。

##全探索
###[How many ways?](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B&lang=ja)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    while(true){
        int n, x;
        cin >> n >> x;
        
        if(n ==0 && x==0) break;
        
        int ans=0;
        for(int i=1; i<=n; i++){
            for(int j=i+1; j<=n-1; j++){
                for(int k=j+1; k<=n; k++){
                    if(x == i+j+k) ans++;
                }
            }
        }
        
        cout << ans << endl;
    }

    return 0;
}
```

###[B - 105](https://atcoder.jp/contests/abc106/tasks/abc106_b)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll =long long;
using P = pair<int,int>;
 
int main(int argc, const char * argv[]) {
    int N;
    cin >> N;
    
    int ans=0;
    for(int i=1; i<=N; i+=2){
        int c=0;
        for(int j=1; j<=i; j++){
            if(i%j==0) c++;
        }
        if(c==8) ans++;
    }
    
    cout << ans << endl;
 
    return 0;
}
```

###[B - ATCoder](https://atcoder.jp/contests/abc122/tasks/abc122_b)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    
    string s;
    cin >> s;
    
    int max_l=0;
    int l=0;
    rep(i, s.length()){
        char ch = s[i];
        if('A'==ch || 'C'==ch || 'G'==ch || 'T'==ch){
            l++;
        }else{
            max_l = max(max_l, l);
            l=0;
        }
    }
    
    max_l = max(max_l, l);
    cout << max_l << endl;

    return 0;
}
```

###[C - カラオケ](https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

ll A[100][100];

int main(int argc, const char * argv[]) {
    int N, M;
    cin >> N >> M;
    
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> A[i][j];
        }
    }
    
    ll ans=0;
    for(int i=0; i<M-1; i++){
        for(int j=i+1; j<M; j++){
            ll sum=0;
            for(int k=0; k<N; k++){
                sum += max(A[k][i], A[k][j]);
            }
            ans = max(ans, sum);
        }
    }
    
    cout << ans << endl;

    return 0;
}
```

##工夫して通り数を減らす全列挙
###[C - Half and Half](https://atcoder.jp/contests/abc095/tasks/arc096_a)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

ll A[100][100];

int main(int argc, const char * argv[]) {
    int A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;
    
    int money = A * X + B * Y;
    money = min(money, C * max(X, Y) * 2);
    if(X>Y) money = min(money, C * Y * 2 +  A * (X - Y));
    else money = min(money, C * X * 2 +  B * (Y - X));
    cout << money << endl;

    return 0;
}
```

###[D - Lucky PIN](https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
 
int main(int argc, const char * argv[]) {
    int N;
    string S;
    cin >> N >> S;
    
    int ans=0;
    rep(i, 10){
        rep(j, 10){
            rep(k, 10){
                bool ok1 = false;
                bool ok2 = false;
                bool ok3 = false;
                rep(s, N){
                    int l = stoi(S.substr(s, 1));
                    if(k == l && ok2) ok3 = true;
                    else if(j == l && ok1) ok2 = true;
                    else if(i == l) ok1 = true;
                        
                    if(ok1 && ok2 && ok3){
                        ans+=1;
                        break;
                    }
                }
            }
        }
    }
    
    cout << ans << endl;
    
    return 0;
}
```

##ビット全探索
###[Exhaustive Search](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=ja)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int n, q;
    cin >> n;
    vector<int> A(n);
    rep(i, n){
        cin >> A[i];
    }

    cin >> q;
    vector<int> M(q);
    vector<bool> res(q);
    rep(i, q){
        cin >> M[i];
        res[i]=false;
    }

    for(int bit=0; bit<(1<<n); bit++){
        int sum=0;
        for(int a=0; a<n; a++){
            if(bit>>a&1){
                sum+=A[a];
            }
        }
        for(int m=0; m<q; m++){
            if(M[m] == sum) res[m] = true;
        }
    }
    
    for(int m=0; m<q; m++){
        if(res[m]) cout << "yes" << endl;
        else cout << "no" << endl;
    }
    return 0;
}
```

###[C - Switches](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=ja)

```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)
#define pai 3.1415926535897932384
 
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;
    
    vector<vector<int>> light_bulb(M);
    rep(i, M){
        int K;
        cin >> K;
        rep(j, K){
            int k;
            cin >> k;
            k--;
            light_bulb[i].push_back(k);
        }
    }
    
    vector<int> p(M);
    rep(i, M){
        cin >> p[i];
    }
    
    int ans=0;
    for(int bit=0; bit<(1<<N); bit++){
        vector<int> push_light_bulb(M, 0);
        for(int i=0; i<N; i++){
            if(bit>>i&1){
                rep(j, light_bulb.size()){
                    rep(k, light_bulb[j].size()){
                        if(i==light_bulb[j][k]){
                            push_light_bulb[j]++;
                        }
                    }
                }
            }
        }
        
        bool res=true;
        rep(j, push_light_bulb.size()){
            if(p[j]!=push_light_bulb[j]%2){
                res=false;
            }
        }
        if(res) ans++;
    }
    
    cout << ans << endl;
    
    return 0;
}
```

###[D - 派閥](https://atcoder.jp/contests/abc002/tasks/abc002_4)
無向性グラフを使います。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

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};
    rep(i, M){
        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;
}
```

バチャで全部解いた問題。
履歴が残ってる...。