AtCoder Beginner Contest 272

## [A - Integer Sum](https://atcoder.jp/contests/abc272/tasks/abc272_a)

O(N)
0<=i<NのA[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);
    rep(i, N) cin >> A[i];
    ll ans=0;
    rep(i, N) ans += A[i];  
    cout << ans << endl;
    return 0;
} 
```

## [B - Everyone is Friends](https://atcoder.jp/contests/abc272/tasks/abc272_b)

O(N^2)
N<=100の制約なので全探索で間に合います。

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

bool graph[101][101];

int main() {
    int N, M;
    cin >> N >> M;
    rep(i, M){
        int k;
        cin >> k;
        vector<int> x(k);
        rep(j, k) cin >> x[j];
        rep(p, k-1){
            repx(q, p+1, k){
                graph[x[p]][x[q]] = true;
                graph[x[q]][x[p]] = true;
            }
        }
    }

    bool ok = true;
    repx(p, 1, N+1){
        repx(q, p+1, N+1){
            if(graph[p][q] == false) ok = false;
        }
    }
    
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
} 
```

## [C - Max Even](https://atcoder.jp/contests/abc272/tasks/abc272_c)

O(N)
2<=N<=2×10^5なので全探索だとTLEします。
偶数になる条件は、偶数＋偶数、奇数＋奇数です。
odd, evenの各最大値から２つ取り出しmax()を判定。

```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;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];

    vector<ll> odd, even;
    rep(i, N){
        if(A[i]%2==0) odd.push_back(A[i]);
        else even.push_back(A[i]);
    }
    sort(odd.begin(), odd.end());
    sort(even.begin(), even.end());

    ll ans=-1;
    if(odd.size()>1) ans = odd[odd.size()-1] + odd[odd.size()-2];
    if(even.size()>1) ans = max(ans, even[even.size()-1] + even[even.size()-2]);
    cout << ans << endl;
    return 0;
} 
```

## [D - Root M Leaper](https://atcoder.jp/contests/abc272/tasks/abc272_d)

O(N*N)
400*400=160000を、O((N*N)^2)するとTLEになります。
この問題は、移動距離の組み合わせを事前に計算してbfsすると解答できます。

```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<ll,ll>;
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 dx[4] = {1, 1, -1, -1};
ll dy[4] = {1, -1, 1, -1};

ll graph[401][401];

int main() {
    ll N, M;
    cin >> N >> M;

    vector<P> dict;
    for(ll x=0; x*x<=M; x++){
        for(ll y=0; x*x + y*y<=M; y++){
            if(x*x+y*y == M){
                dict.push_back(P(x, y));
            }
        }
    }

    repx(i, 1, N+1) repx(j, 1, N+1) graph[i][j] = -1;
    queue<P> que;
    que.push(P(1, 1));
    graph[1][1] = 0;

    while(que.size()){
        P p = que.front();
        que.pop();

        for(auto d:dict){
            for(int i=0; i<4; i++){
                ll k = p.first + d.first * dx[i];
                ll l = p.second + d.second * dy[i];

                if(k<1 || N<k || l<1 || N<l) continue;
                if(graph[k][l] > -1) continue;
                graph[k][l] = graph[p.first][p.second] + 1;
                que.push(P(k, l));
            }
        }
    }

    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cout << graph[i][j];
            if(j<N) cout << ' ';
        }
        cout << endl;
    }

    return 0;
} 
```