AtCoder Beginner Contest 385

## [A - Equally](https://atcoder.jp/contests/abc385/tasks/abc385_a)

O(1)
Aの配列を昇順にソートします。

```math
A_0 + A_1 = A_2
```
```math
A_0 = A_1 = A_2
```

の時に`Yes`です

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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 = 3;
    vector<int> v(n);
    rep(i, n) cin >> v[i];
    sort(v.begin(), v.end());

    if(v[2] == v[1] + v[0] || v[2] == v[1] && v[1] == v[0]){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
} 
```

## [B - Santa Claus 1](https://atcoder.jp/contests/abc385/tasks/abc385_b)

O(N)
シミュレートしましょう。
Tの文字列の通りにパターン分けして座標を更新します。
'@'を探索した時、'.'へ更新して一度のみの判定にしましょう。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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 H, W, X, Y;
    cin >> H >> W >> X >> Y;
    X--; Y--;
    vector<string> S(H);
    rep(i, H) cin >> S[i];
    string T;
    cin >> T;

    int ans = 0;
    rep(i, T.size()){
        int nx = X, ny = Y;
        if('U' == T[i]) nx--;
        if('D' == T[i]) nx++;
        if('L' == T[i]) ny--;
        if('R' == T[i]) ny++;
        if(S[nx][ny] == '#') continue;
        X = nx, Y = ny;
        if(S[X][Y] == '@'){
            S[X][Y] = '.';
            ans++;
        }
    }
    cout << X+1 << ' '<< Y+1 << ' ' << ans << endl;
 
    return 0;
} 
```

## [C - Illuminate Buildings](https://atcoder.jp/contests/abc385/tasks/abc385_c)

多分O(N^2)
最初の２つの等間隔に並んでいるビルを探索します。
２つのビルを基準に、等間隔に並んでいるビルを探索します。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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> H(N);
    rep(i, N) cin >> H[i];

    int ans = 1;
    for(int i=0; i<N; i++){
        for(int j=i+1; j<N; j++){
            if(H[i] == H[j]){
                int cnt = 2;
                int d = j - i;
                while(j+d < N && H[j+d] == H[i]){
                    d+=j-i;
                    cnt++;
                }
                ans = max(ans, cnt);
            }
        }
    }
    cout << ans << endl;

    return 0;
} 
```

## [D - Santa Claus 2](https://atcoder.jp/contests/abc385/tasks/abc385_d)

O(MlogN)
x軸を基準に家を管理するデータ構造w、y軸のを基準に家を管理するデータ構造hを用意します。
`map<long long, set<long long>>`のデータ構造が適しています。
二分探索で、移動する直線上の要素を探索します。
w, hのデータ構造から要素を削除し、カウントを計測します。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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, sx, sy;
    cin >> n >> m >> sx >> sy;
    map<ll, set<ll>> h, w;
    rep(i, n){
        ll x, y;
        cin >> x >> y;
        w[x].insert(y);
        h[y].insert(x);
    }

    ll x = sx, y = sy;
    ll ans = 0;
    rep(i, m){
        char d;
        ll c;
        cin >> d >> c;
        if('U' == d){
            ll dy = y + c;
            auto l = w[x].lower_bound(y);
            while(l != w[x].end() && *l <= dy){
                h[*l].erase(x);
                l = w[x].erase(l);
                ans++;
            }
            y = dy;
        }
        if('D' == d){
            ll dy = y - c;
            auto l = w[x].lower_bound(dy);
            while(l != w[x].end() && *l <= y){
                h[*l].erase(x);
                l = w[x].erase(l);
                ans++;
            }
            y = dy;
        }
        if('L' == d){
            ll dx = x - c;
            auto l = h[y].lower_bound(dx);
            while(l != h[y].end() && *l <= x){
                w[*l].erase(y);
                l = h[y].erase(l);
                ans++;
            }
            x = dx;
        }
        if('R' == d){
            ll dx = x + c;
            auto l = h[y].lower_bound(x);
            while(l != h[y].end() && *l <= dx){
                w[*l].erase(y);
                l = h[y].erase(l);
                ans++;
            }
            x = dx;
        }
    }
    cout << x << ' ' << y << ' ' << ans << endl;

    return 0;
} 
```