AtCoder Beginner Contest 236

A - chukodai

(1)
a番目とb番目の文字を入れ替える。

C++

# include <bits/stdc++.h>
 
# define rep(i,n) for(int i=0; i<(n); ++i)
# define repx(i,x,n) for(int i=x; i<(n); ++i)
# define fixed_setprecision(n) fixed << setprecision((n))
# define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
# define pai 3.1415926535897932384
# define NUM_MAX 2e18
# define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
 
int main() {
    string s;
    cin >> s;
    int a, b;
    cin >> a >> b;
    
    a--;
    b--;
 
    char t = s[a];
    s[a] = s[b];
    s[b] = t; 
 
    cout << s << endl;
 
    return 0;
}

B - Who is missing?

O(N)
連想配列でどの数字が何個ほど存在するかカウントする。
１枚足りないカードを表示する。

C++

# include <bits/stdc++.h>
 
# define rep(i,n) for(int i=0; i<(n); ++i)
# define repx(i,x,n) for(int i=x; i<(n); ++i)
# define fixed_setprecision(n) fixed << setprecision((n))
# define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
# define pai 3.1415926535897932384
# define NUM_MAX 2e18
# define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
 
int main() {
    int N;
    cin >> N;
 
    map<int, int> mp;
    rep(i, 4*N-1){
        int a;
        cin >> a;
        mp[a]++;
    }
 
    int ans=0;
    for(auto m:mp){
        if(m.second==3){
            ans=m.first;
        }
    }
    cout << ans << endl;
 
    return 0;
}

C - Route Map

O(N)
配列と連想配列を用意する。
配列には駅を昇順に格納する。
連想配列には、普通列車で止まる駅をカウント、また急行列車で止まる駅のカウントを行う。
配列をループし、連想配列のキーが２個カウントされた駅はYes、異なるならNoを表示する。

C++

# include <bits/stdc++.h>
 
# define rep(i,n) for(int i=0; i<(n); ++i)
# define repx(i,x,n) for(int i=x; i<(n); ++i)
# define fixed_setprecision(n) fixed << setprecision((n))
# define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
# define pai 3.1415926535897932384
# define NUM_MAX 2e18
# define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
 
int main() {
    int N, M;
    cin >> N >> M;
    vector<string> S(N);
    map<string, int> mp;
    rep(i, N){
        cin >> S[i];
        mp[S[i]]++;
    }
    rep(i, M){
        string t;
        cin >> t;
        mp[t]++;
    }
 
    for(auto s:S){
        if(mp[s]==2) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
 
    return 0;
}

D - Dance

C++

# include <bits/stdc++.h>
 
# define rep(i,n) for(int i=0; i<(n); ++i)
# define repx(i,x,n) for(int i=x; i<(n); ++i)
# define fixed_setprecision(n) fixed << setprecision((n))
# define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
# define pai 3.1415926535897932384
# define NUM_MAX 2e18
# define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

ll N;
ll graph[16][16];
bool used[16];
vector<pair<int, int>> vec;
ll res;

void dfs(){

    if(vec.size()==N){
        ll ans=0;
        for(auto v:vec){
            ans^=graph[v.first][v.second];
        }
        res = max(res, ans);
        return;
    }

    int l;
    rep(i, 2*N){
        if(!used[i]){
            l=i;
            break;
        }
    }

    used[l] = true;
    repx(i, 1, 2*N){
        if(!used[i]){
            vec.push_back(P(l, i));
            used[i] = true;
            dfs();
            used[i] = false;
            vec.pop_back();
        }
    }
    used[l] = false;
}

int main() {
    
    cin >> N;
    vector<int> parson(2*N);
    rep(i, 2*N) parson[i]=0;

    rep(i, 2*N-1){
        repx(j, i+1, 2*N){
            cin >> graph[i][j];
        }
    }
    dfs();
    cout << res << endl;

    return 0;
}