AtCoder Beginner Contest 301


## [A - Overall Winner](https://atcoder.jp/contests/abc301/tasks/abc301_a)

O(N)
先に(N+1)/2の数を計測した方が勝ちになります。

```C++: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, T=0, A=0;
    cin >> N;
    string s;
    cin >> s;

    rep(i, N){
        if(s[i] == 'T') T++;
        if(s[i] == 'A') A++;
        if(T == (N+1) / 2){
            cout << 'T' << endl;
            return 0;
        }
        if(A == (N+1) / 2){
            cout << 'A' << endl;
            return 0;
        }
    }

    return 0;
} 
```

## [B - Fill the Gaps](https://atcoder.jp/contests/abc301/tasks/abc301_b)

O(N)
i+1とiの配列を比べて、新規で配列を作成しましょう。

```C++: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), ans;
    rep(i, N) cin >> A[i];

    rep(i, N-1){
        
        ans.push_back(A[i]);

        if(A[i+1]-A[i] > 1){
            for(int j=1; j<=abs(A[i]-A[i+1])-1; j++){
                ans.push_back(A[i]+j);
            }
        }
        if(A[i+1]-A[i] < -1){
            for(int j=1; j<=abs(A[i]-A[i+1])-1; j++){
                ans.push_back(A[i]-j);
            }
        }
    }
    ans.push_back(A[N-1]);

    rep(i, ans.size()){
        cout << ans[i];
        if(ans.size()-1 != i) cout << ' ';
    }
    cout << endl;

    return 0;
} 
```

## [C - AtCoder Cards](https://atcoder.jp/contests/abc301/tasks/abc301_c)

O(N)
mapを使い、S,Tの文字列で一致しない文字Aiを計測。
一致しない文字Aiの数が正の数なら、Tの@の数をその分だけ減算。
一致しない文字Aiの数が負の数なら、Sの@の数をその分だけ加算。
S,Tの@の数が０以上か、S,Tの@の数が等しいかの両方を満たすならイカサマできます。

```C++: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;

    string atcoder="atcoder";
    int N = s.size();
    int gs=0;
    int gt=0;
    map<char, int> mp;
    rep(i, N){
        if(s[i] != '@') mp[s[i]]++;
        if(t[i] != '@') mp[t[i]]--;
        if(s[i] == '@') gs++;
        if(t[i] == '@') gt++;
    }

    for(P m:mp){
        if(m.second==0) continue;
        if(atcoder.find(m.first) == string::npos){
            cout << "No" << endl;
            return 0;
        }
        if(m.second > 0) gt -= m.second;
        if(m.second < 0) gs += m.second;
    }

    if(gt == gs && gt>=0 && gs>=0) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
} 
```

## [D - Bitmask](https://atcoder.jp/contests/abc301/tasks/abc301_d)

O(N)
この問題は、最大値から考察していきました。
N=1000000000000000000
S=????????????????????????????????????????????????????????????
の時、
N^18までの数を10進数で1ずつ比較するとTLEになります。
普通には回答できません。

2進数の問題ですので、2進数の重みを使用してみましょう。
2^59, 2^58, 2^57....2^0
を計測していく方法ではO(60)で文字列を処理できます。
この方法でできないか考察していきます。

S=??111111??

では、1の重みは必ず計測する必要があります。
前処理で各桁の重みを計算しましょう。

その後に、
?を桁を１として重みを加算したときに、Nを超えないなら加算しましょう。

O(120)のループでいけそうですね。
この問題は、２進数の計算に慣れているかの問題だとわかります。

```C++: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; }

/* 
name: modPow
proc: 高速なべき乗
*/
ll modPow(ll a, ll n, ll mod){
    ll res = 1;
    while(n>0){
        if(n&1) res = res * a % mod;
        a = a * a % mod;
        n = n>>1;
    }
    return res;
}

int main() {
    string s;
    cin >> s;
    ll N;
    cin >> N;

    ll s_max = s.size();
    ll total_s = 0;
    for(ll i=0; i<s_max; i++){
        if(s[i] == '1'){
            total_s += modPow(2, s_max-i-1, 1000000000000000000);
        }
    }
    for(ll i=0; i<s_max; i++){
        if(s[i] == '?'){
            if(total_s + modPow(2, s_max-i-1, 1000000000000000000) <= N){
                total_s += modPow(2, s_max-i-1, 1000000000000000000);
            }
        }
    }
    if(N<total_s) cout << -1 << endl;
    else cout << total_s << endl;

    return 0;
} 
```