レッドコーダーが教える、競プロ・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;
}

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