AtCoder Beginner Contest 349

A - Zero Sum Game

負け数と勝ち数が同一の数になりますね。
Aiの合計を検索し、符号を逆転させた数が人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;
    vector<int> A(N-1);
    rep(i, N-1) cin >> A[i];

    int ans=0;
    rep(i, N-1) ans += A[i];
    cout << -ans << endl;

    return 0;
} 

B - Commencement

O(N)
文字が何回現れたか検索。
N回現れた文字は何種類か検索。
２種類以外の回数があるなら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() {
    string s;
    cin >> s;
    map<char, int> mp;

    rep(i, s.size()){
        mp[s[i]]++;
    }

    map<int, int> ans;
    for(auto m:mp){
        ans[m.second]++;
    }
    for(auto a:ans){
        if(a.second != 2){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;

    return 0;
} 

C - Airport Code

O(N)
素直にシミュレートしましょう。
文字を大文字に変換。
順番に空港コードの文字が存在するか検索。
最後の文字が'X'ならYes。
２文字まで一緒なら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() {
    string S, T;
    cin >> S >> T;

    int N = S.size();
    int cnt = 0;
    rep(i, N){
        char a = S[i] - 32;

        if(T[cnt] == a) cnt++;
        if(cnt==3){
            cout << "Yes" << endl;
            return 0;
        }
    }
    if(cnt == 2 && T[2] == 'X'){
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;

    return 0;
} 

D - Divide Interval

dfsです。
言語化するのはとっても難しい。

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

set<pair<ll, ll>> st;

void dfs(ll l, ll r, ll L, ll R){
    if(L <= l && r <= R){
        st.insert(pair<ll, ll>(l, r));
        return;
    }
    ll m = (l + r) / 2;
    if(R<=m){
        dfs(l, m, L, R);
        return;
    }
    if(m<=L){
        dfs(m, r, L, R);
        return;
    }
    dfs(l, m, L, R);
    dfs(m, r, L, R);
}


int main() {
    ll L, R;
    cin >> L >> R;
    ll m = 1;
    rep(i, 60) m *= 2;
    dfs(0, m, L, R);
    cout << st.size() << endl;
    for(auto s:st){
        cout << s.first << ' ' << s.second << endl;
    }
    return 0;
}