Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@RubyLrving(ruby lrving)

全探索の問題

Last updated at Posted at 2020-06-07

#全探索を復習
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】

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

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

##全探索の問題
###B - 81

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

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

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

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

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

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

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

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

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

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

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

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

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

  • 無効グラフを使います。
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。
残った問題は後日に追記します。

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

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?