AtCoder Beginner Contest 277

## [A - ^{-1}](https://atcoder.jp/contests/abc277/tasks/abc277_a)

O(N)

Piのindexを管理します。

```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, X;
    cin >> N >> X;
    map<int, int> mp;
    rep(i, N){
        int p;
        cin >> p;
        mp[p] = i+1;
    }
    cout << mp[X] << endl;
    return 0;
} 
```

## [B - Playing Cards Validation](https://atcoder.jp/contests/abc277/tasks/abc277_b)

O(N)

１、同じ文字列が存在するかチェックを行います。
２、その上で１文字目、２文字目の文字のチェックを行います。

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

char ch1[4] = {'H' , 'D' , 'C' , 'S'};
char ch2[13] = {'A' , '2' , '3' , '4' , '5' , '6' , '7' , '8' , '9' , 'T' , 'J' , 'Q' , 'K'};

int main() {
    int N;
    cin >> N;
    map<char, int> mp1, mp2;
    rep(i, 4) mp1[ch1[i]] = 1;
    rep(i, 13) mp2[ch2[i]] = 1;

    set<string> st;
    rep(i, N){
        string s;
        cin >> s;
        if(st.find(s) == st.end()){
            st.insert(s);
        }else{
            cout << "No" << endl;
            return 0;           
        }
    }

    for(auto s:st){
        if(mp1.find(s[0]) == mp1.end() || mp2.find(s[1]) == mp2.end()){
            cout << "No" << endl;
            return 0;
        }  
    }
    cout << "Yes" << endl;

    return 0;
} 
```

## [C - Ladder Takahashi](https://atcoder.jp/contests/abc277/tasks/abc277_c)

O(N)
dfsかbfsを使用します。
この問題はビルの階数にもmap（ハッシュ）を使用することです。

```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;
    map<int, vector<int>> graph;
    rep(i, N){
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    queue<int> que;
    que.push(1);
    set<int> st;
    int ans=1;
    while(que.size()){
        int p = que.front();
        que.pop();
        if(graph.find(p) == graph.end()) continue;
        int n = graph[p].size();
        rep(i, n){
            int q = graph[p][i];
            if(st.find(q) != st.end()) continue;
            st.insert(q);
            que.push(q);
            ans = max(ans, q);
        }
    }
    cout << ans << endl;
    return 0;
} 
```

## [D - Takahashi's Solitaire](https://atcoder.jp/contests/abc277/tasks/abc277_d)

O(N)
整数問題です。
各余りを示すカードの合計を計算します。
余りxに対して、x+1が存在するか判定します。
存在していたなら数を合計Yを計算します。
Yの最大値を比べます。

```
a = A[i] % M
```

```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() {
    ll N, M, all=0;
    cin >> N >> M;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    map<ll, ll> mp;
    rep(i, N){
        ll a = A[i] % M;
        mp[a] += A[i];
        all += A[i];
    }

    ll cnt=0;
    ll old=0;
    if(mp.find(0) == mp.end()) old = mp.begin()->first;
    vector<ll> res(1, 0);
    for(auto m:mp){
        if(old == m.first || old+1 == m.first) res[cnt] += m.second;
        else cnt++, res.push_back(m.second);
        old = m.first;
    }
    ll ans=0;
    for(auto r:res){
        ans = max(ans, r);
    }
    if(mp.find(0) != mp.end() && res.size() > 1) ans = max(ans, res[0] + res[cnt]);
    cout << all - ans << endl;

    return 0;
} 
```