全探索の問題

#全探索を復習
[レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】](https://qiita.com/e869120/items/f1c6f98364d1443148b3#1-6-4-%E5%85%A8%E6%8E%A2%E7%B4%A2%E3%81%AB%E6%85%A3%E3%82%8C%E3%82%8B)

プログラミングコンテストチャレンジブックと並行して上記の記事を学習していきます。
モチベーションの維持の目的です。
プログラミングコンテストチャレンジブックは難しい。

そしてたまには解かないと忘れてしまいます。

##全探索の問題
###[B - 81](https://atcoder.jp/contests/abc144/tasks/abc144_b)

```python:python
from math import floor
from decimal import Decimal

N = int(input())

for i in range(1, 10):
    for j in range(1, 10):
        if(N == i * j):
            print("Yes")
            break
    else:
        continue
    break
else:
    print("No")
```

###[B - Count ABC](https://atcoder.jp/contests/abc150/tasks/abc150_b)

```python:python
N = input()
S = input()
T = "ABC"

res=0
for i in range(0, len(S)):
    if S[i:i+len(T)]==T:
        res+=1

print(res)
```

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

```python:python
S = input()

ans=0
res=0
for i in range(0, len(S)):
    if(S[i]=='A' or  S[i]=='C' or S[i]=='G' or S[i]=='T'):
        res+=1
    else:
        ans = max(res, ans)
        res = 0

ans = max(res, ans)
print(ans)
```

###[B - Uneven Numbers](https://atcoder.jp/contests/abc136/tasks/abc136_b)

```python:python
N = int(input())

res=0
for i in range(1, N+1):
    if(len(str(i))%2==1):
        res+=1

print(res)
```

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

```python:python
N = int(input())

ans=0
for i in range(1, N+1):
    res=0
    for j in range(1, i+1):
        if(i%j==0):
            res+=1
    if(res==8 and i%2==1):
        ans+=1

print(ans)
```

###[B - K-th Common Divisor](https://atcoder.jp/contests/abc120/tasks/abc120_b)

```python:python
A, B, K = list(map(int, input().split()))

ans=0
res=0
for i in range(min(A, B), 0, -1):
    if A%i==0 and B%i==0:
        res+=1
        if res==K:
            ans=i
            break

print(ans)
```

###[C - Digits in Multiplication](https://atcoder.jp/contests/abc057/tasks/abc057_c)

```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[]) {
    ll N;
    cin >> N;
    
    int ans = to_string(N).length();
    for(ll i=1; i*i<=N; i++){
        ll A = i;
        if(N%A==0){
            int a = to_string(A).length();
            int b = to_string(N/A).length();
            ans = min(ans, max(a, b));
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

```

###[C - Half and Half](https://atcoder.jp/contests/abc095/tasks/arc096_a)

```python:python
A, B, C, X, Y = list(map(int, input().split()))

ans = A*X + B*Y
c = min(X, Y)
ans = min(A*(X-c) + B*(Y-c) + c*C*2, ans)
c = max(X, Y)
ans = min(c*C*2, ans)

print(ans)
```

###[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<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;
    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;
}
```

###[C - Switches](https://atcoder.jp/contests/abc128/tasks/abc128_c)

```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;
}
```

###[C - HonestOrUnkind2](https://atcoder.jp/contests/abc147/tasks/abc147_c)

```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;
    cin >> N;
    
    vector<vector<P>> A(N);
    rep(i, N){
        int a;
        cin >> a;
        
        rep(j, a){
            int x, y;
            cin >> x >> y;
            A[i].push_back(P(--x, y));
        }
    }
    
    int ans=0;
    for(int bit=0; bit<(1<<N); bit++){
        bool ok=true;
        int res=0;
        for(int i=0; i<N; i++){
            if(bit>>i&1){
                for(int j=0; j<A[i].size(); j++){
                    int x = A[i][j].first;
                    int y = A[i][j].second;
                    
                    if(y==1&&!(bit>>x&1)) ok=false;
                    if(y==0&&(bit>>x&1)) ok=false;
                }
                if(ok) res+=1;
            }
        }
        if(ok) ans = max(ans, res);
    }
    
    cout << ans << endl;
    
    return 0;
}

```

###[C - Average Length](https://atcoder.jp/contests/abc145/tasks/abc145_c)

```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>;

#define MAX_N 8

int perm[MAX_N];
vector<P> pos;


void permutation(int n){
    for(int i=0; i<n; i++){
        perm[i]=i;
    }
    
    double ans=0;
    double count=0;
    do{
        /* ここにpermの処理を書く */
        for(int i=0; i+1<n; i++){
            int x1 = pos[perm[i]].first;
            int y1 = pos[perm[i]].second;
            int x2 = pos[perm[i+1]].first;
            int y2 = pos[perm[i+1]].second;
            
            ans += (double)sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
        }
        count++;
        
    }while(next_permutation(perm, perm+n));
    
    cout << setprecision(15) << ans/count << endl;
}

int main(int argc, const char * argv[]) {
    int N;
    cin >> N;
    
    rep(i, N){
        P p;
        cin >> p.first >> p.second;
        pos.push_back(p);
    }
    
    permutation(N);
    
    return 0;
}
```

###[C - Count Order](https://atcoder.jp/contests/abc150/tasks/abc150_c)

```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>;

#define MAX_N 8
int perm[MAX_N];
int perm_P[MAX_N];
int perm_Q[MAX_N];
int N;


void permutation(int n){
    for(int i=0; i<n; i++){
        perm[i]=i+1;
    }
    int count=0;
    int p_index=0;
    int q_index=0;
    do{
        bool is_perm_P=true;
        bool is_perm_Q=true;
        /* ここにpermの処理を書く */
        for(int i=0; i<n; i++){
            if(perm[i]!=perm_P[i]) is_perm_P=false;
            if(perm[i]!=perm_Q[i]) is_perm_Q=false;
        }
        
        count++;
        if(is_perm_P) p_index=count;
        if(is_perm_Q) q_index=count;
        
    }while(next_permutation(perm, perm+n));
    
    cout << abs(p_index-q_index) << endl;
}

int main(int argc, const char * argv[]) {
    
    cin >> N;
    rep(i, N){
        cin >> perm_P[i];
    }
    rep(i, N){
        cin >> perm_Q[i];
    }
    
    permutation(N);

    return 0;
}
```

###[ABC 054 C One-stroke Path](https://atcoder.jp/contests/abc054/tasks/abc054_c)

- 無効グラフを使います。

```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>;

#include<algorithm>
#define MAX_N 8
bool G[MAX_N][MAX_N] = {false};
int order[MAX_N];

void permutation(int n){
    for(int i=0; i<n; i++){
        order[i]=i;
    }
    
    int res=0;
    do{
        if(order[0] != 0) continue;
        bool ok=true;
        /* ここにpermの処理を書く */
        for(int i=0; i+1<n; i++){
            int from = order[i];
            int to = order[i+1];
            
            if(!G[from][to]) ok=false;
        }
        if(ok) res++;
    }while(next_permutation(order, order+n));
    
    cout << res << endl;
}

int main(int argc, const char * argv[]) {
    int n, m;
    cin >> n >> m;
    
    rep(i, m){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        G[a][b]=true;
        G[b][a]=true;
    }
    
    permutation(n);
    
    return 0;
}

```

#目標
感謝の１日一回AC。
残った問題は後日に追記します。

###追記
全ての問題を解き終えました。
茶色を目指す為の基礎ができたと感じています。