AtCoder Beginner Contest 348

## [A - Penalty Kick](https://atcoder.jp/contests/abc348/tasks/abc348_a)

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

int main() {
    int N;
    cin >> N;

    for(int i=1; i<=N; i++){
        if(i%3==0) cout << 'x';
        else cout << 'o';
    }
    cout << endl;

    return 0;
} 
```

## [B - Farthest Point](https://atcoder.jp/contests/abc348/tasks/abc348_b)

O(N)
各点の、
(x2 - x1) ^ 2 + (y2 - y1) ^ 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;
    cin >> N;
    vector<int> X(N), Y(N);
    rep(i, N) cin >> X[i] >> Y[i];

    for(int i=0; i<N; i++){
        int XY=0;
        int index=0;
        for(int j=0; j<N; j++){

            if(i==j) continue;

            if(XY < (X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j])){
                XY = max(XY, (X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j]));
                index = j;
            }

        }
        cout << index+1 << endl;
    }

    return 0;
} 
```

## [C - Colorful Beans](https://atcoder.jp/contests/abc348/tasks/abc348_c)

各色の最小値を探索する。
探索した要素の中から最大の値を出力する。

```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, int> mp;
    for(int i=0; i<N; i++){
        int a, c;
        cin >> a >> c;
        if(mp.find(c) == mp.end()){
            mp[c] = a;
        }else{
            mp[c] = min(mp[c], a);
        }
    }
    int ans=0;
    for(auto m:mp){
        ans = max(ans, m.second);
    }
    cout << ans << endl;

    return 0;
} 
```

## [D - Medicines on Grid](https://atcoder.jp/contests/abc348/tasks/abc348_d)

O(N)
bfsです。
エネルギーの残量を記録するテーブルAを作成します。

テーブルの更新条件は、
・移動先のマスが　'.'である
・移動先のマスに関するテーブルAの値は、移動前のマスに関するテーブルA未満である

キューに追加する条件は、
・移動先のマスが　'.'である
・移動先のマスに関するテーブルAの値は、移動前のマスに関するテーブルAの値-1より値が小さい

薬を使用する条件は、
・現在のマスに関するテーブルAの値は、薬の値より小さい

薬を使用した、また使用する必要がなかった際には、
・薬のエネルギーを0にする

上記の条件を導くことができると解く事ができます。

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

int main() {
    int H, W, N;
    cin >> H >> W;
    vector<string> A(H);
    rep(i, H) cin >> A[i];

    int sx, sy, tx, ty;
    rep(i, H) rep(j, W){
        if(A[i][j] == 'S') sx = j, sy = i;
        if(A[i][j] == 'T') tx = j, ty = i;
    }

    cin >> N;
    map<P, int> mp;
    rep(i, N){
        int r, c, e;
        cin >> r >> c >> e;
        mp[P(--r, --c)] = e;
    }

    // Queueを生成
    queue<P> que;
    // 最初の要素をキューに追加
    que.push(P(sy, sx));

    // キューの要素がなくまるまで処理を行う
    while(que.size()){
        // 最初の要素を取り出す
        P p = que.front();
        que.pop();

        // 薬の使用
        if(mp.find(P(p.first, p.second)) != mp.end()){
            if(d[p.first][p.second] < mp[P(p.first, p.second)]){
                d[p.first][p.second] = mp[P(p.first, p.second)];
            }
            mp[P(p.first, p.second)] = 0;
        }

        // 処理に適した繰り返し処理
        for(int i=0; i<4; i++){
            // 何かしらの処理
            int ny = p.first + dy[i];
            int nx = p.second + dx[i];

            if(ny>=H || ny<0 || nx >= W || nx < 0 || d[p.first][p.second] <= 0 || A[ny][nx] == '#') continue;

            // キューに追加する条件
            if(A[ny][nx] == '.' && d[ny][nx] < d[p.first][p.second]){
                // キューに追加
                if(d[ny][nx] < d[p.first][p.second] - 1 || d[ny][nx]==0) que.push(P(ny, nx));
                // 何かしらの処理
                d[ny][nx] = d[p.first][p.second] - 1;
            }
            if(A[ny][nx] == 'T'){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;

    return 0;
}
```