マイナビプログラミングコンテスト2021（AtCoder Beginner Contest 201）

##[A - Tiny Arithmetic Sequence](https://atcoder.jp/contests/abc201/tasks/abc201_a)

O(1)
ソートを忘れて1WA。
これがなかったら緑パフォーマンスでした。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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() {
    vector<int> a(3);
    cin >> a[0] >> a[1] >> a[2];
 
    sort(a.begin(), a.end());
 
    if(abs(a[2] - a[1]) == abs(a[1] - a[0])) cout << "Yes" << endl;
    else cout << "No" << endl;
 
    return 0;
}
```

##[B - Do you know the second highest mountain?](https://atcoder.jp/contests/abc201/tasks/abc201_b)

O(N)
pairを知っているかどうかです。
ラムダ式を使わなくてもソートだけでいけるかと。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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<pair<int,string>> m(N);
    rep(i, N){
        string s;
        int t;
        cin >> s >> t;
        m[i].first = t;
        m[i].second = s;
    }
 
    sort(m.begin(), m.end(), [](auto const& x, auto const& y)->int{
        return (x>y);
    });
    cout << m[1].second << endl;
 
    return 0;
}
```

##[C - Secret Number](https://atcoder.jp/contests/abc201/tasks/abc201_c)

O(N)
4桁しかないので全探索でいけますね。
公式の解説の手法が正攻法だと思います。

dfsで使用できる全ての数字にて暗証番号を作成。
重複を省くためにsetを使用。
その後、全探索して'o'に該当する数字は全て使われているか判定しました。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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<string> se;
string str;
 
void dfs(string s, int c){
    if(s.length() >= 4){
        se.insert(s);
        return;
    }
    if(str.length() <= c){
        return;
    }
 
    rep(i, str.length()){
        if(str[i] == 'o' || str[i] == '?'){
            dfs(s + to_string(i), c+1);
        }
    }
}
 
int main() {
    cin >> str;
 
    dfs("", 0);
 
    string t;
    rep(i, str.length()){
        if(str[i] == 'o') t += to_string(i);
    }
 
    ll res=0;
    for(const auto& itr:se){
        ll cnt=0;
        rep(i, t.length()){
            if(itr.find(t[i]) == std::string::npos) break;
            cnt++;
        }
        if(cnt==t.length()) res++;
    }
    cout << res << endl;
 
    return 0;
}
```

##[D - Game in Momotetsu World](https://atcoder.jp/contests/abc201/tasks/abc201_d)

O(N)
受け取るDPです。
難しいのは片方の軸の値だけ範囲外にある時です。
その場合はどちらが大きい、小さいか判定せずに固定になります。
欲しい値は、dp[0][0]にて取り出せます。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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 H, W;
char A[2001][2001];
int cost[2001][2001];
int dp[2001][2001];

void solve(){

    if(H==1&&W==1){ cout << "Draw" << endl; return; }

    for(int h=H-1; h>=0; h--){
        for(int w=W-1; w>=0; w--){
            if((h+w)%2==0){
                if(h+1<H && w+1<W) dp[h][w] = max(dp[h+1][w] + cost[h+1][w], dp[h][w+1] + cost[h][w+1]);
                if(h+1>=H && w+1<W) dp[h][w] = dp[h][w+1] + cost[h][w+1];
                if(h+1<H && w+1>=W) dp[h][w] = dp[h+1][w] + cost[h+1][w];
            }else{
                if(h+1<H && w+1<W) dp[h][w] = min(dp[h+1][w] - cost[h+1][w], dp[h][w+1] - cost[h][w+1]);
                if(h+1>=H && w+1<W) dp[h][w] = dp[h][w+1] - cost[h][w+1];
                if(h+1<H && w+1>=W) dp[h][w] = dp[h+1][w] - cost[h+1][w];
            }
        }
    }

    if(dp[0][0]>0) cout << "Takahashi" << endl;
    if(dp[0][0]<0) cout << "Aoki" << endl;
    if(dp[0][0]==0) cout << "Draw" << endl;
}

int main() {
    
    cin >> H >> W;

    rep(i, H) rep(j, W) cin >> A[i][j];
    rep(i, H+1) rep(j, W+1){
        if(A[i][j] == '+') cost[i][j] = 1;
        else if(A[i][j] == '-') cost[i][j] = -1;
        else cost[i][j] = 0;
    }

    solve();

    return 0;
}
```