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)

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

Posted at

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】

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

全探索

How many ways?

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

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

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 - カラオケ

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

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

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

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

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 - 派閥

無向性グラフを使います。

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

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

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?