AtCoder Beginner Contest 384

## [A - aaaadaa](https://atcoder.jp/contests/abc384/tasks/abc384_a)

O(N)
シミュレートしましょう。

```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;
    char c1, c2;
    cin >> N >> c1 >> c2;
    string S;
    cin >> S;

    rep(i, N){
        if(S[i] != c1) S[i] = c2;
    }
    cout << S << endl;

    return 0;
} 
```

## [B - ARC Division](https://atcoder.jp/contests/abc384/tasks/abc384_b)

O(N)
シミュレートしましょう。

```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, R;
    cin >> N >> R;
    
    rep(i, N){
        int d, a;
        cin >> d >> a;
        if(d == 1 && 1600 <= R && R <= 2799){
            R += a;
        }
        if(d == 2 && 1200 <= R && R <= 2399){
            R += a;
        }
    }
    cout << R << endl;

    return 0;
} 
```

## [C - Perfect Standings](https://atcoder.jp/contests/abc384/tasks/abc384_c)

O(2^5+N)
bit全探索と複数条件ソートの問題です。
"ABCDE"の文字を使用して、31パターンの全ての組み合わせを作成します。
アルファベット毎に得点を加算して合計を求めます。
得点＞辞書順の優先順に並び替えて表示します。

自力ACしたコードでは、「bit全探索」を除いて31パターンの全ての組み合わせを用意しています。

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

string use[31] = {
"ABCDE",
"BCDE",
"ACDE",
"ABDE",
"ABCE",
"ABCD",
"CDE",
"BDE",
"ADE",
"BCE",
"ACE",
"BCD",
"ABE",
"ACD",
"ABD",
"ABC",
"DE",
"CE",
"BE",
"CD",
"AE",
"BD",
"AD",
"BC",
"AC",
"AB",
"E",
"D",
"C",
"B",
"A"
};

int main() {
    int N = 5;
    vector<int> v(N);
    rep(i, N) cin >> v[i];

    vector<pair<int, string>> ans;
    rep(i, 31){
        int M = use[i].size();
        int sum = 0;
        rep(j, M){
            int index = use[i][j] - 'A';
            sum += v[index];
        }
        ans.push_back({sum, use[i]});
    }

    sort(ans.begin(), ans.end(), [](const pair<int, string> &x, const pair<int, string> &y){
        return x.first == y.first? x.second > y.second:x.first < y.first;
    });
    reverse(ans.begin(), ans.end());

    rep(i, 31){
        cout << ans[i].second << endl;
    }
   
   return 0;
} 
```

コードを整理しましょう。
アルファベットの組み合わせは、bit全探索で実装します。
得点、文字列のペアをソートして答えを求めます。

```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 = 5;
    vector<int> v(N);
    rep(i, N) cin >> v[i];

    vector<pair<int, string>> ans;
    for(int bit=1; bit<(1 << 5); bit++){
        string s;
        int sum = 0;
        for(int i=0; i<5; i++){
            if(bit >> i & 1){
                sum += v[i];
                s += 'A' + i;
            }
        }
        ans.push_back({-sum, s});
    }

    sort(ans.begin(), ans.end());

    for(auto [score, name]:ans){
        cout << name << endl;
    }
   
   return 0;
} 
```

コンテスト中にこのようなコードが書けるようになりたいですね。

## [D - Repeated Sequence](https://atcoder.jp/contests/abc384/tasks/abc384_d)

O(N)
周期性、連続する区間の問題です。
周期性は余り、連続する区間は尺取り法を使用します。
尺取り法における円循環なので、aの配列をつなげたaaの配列を準備します。
S % Aの合計totalが0なら答えは"Yes"となります。

```C++:C++
    S = S % total;
    if(S == 0){
        cout << "Yes" << endl;
        return 0;
    }
```

尺取り法におけるループの条件は、
- rightがaaのサイズ以下
- 探索中の合計がS未満

```C++:C++
while(right < aa.size() && sum < S)
```

尺取り法の部分を実装しましょう。
`sum == S`なら"Yes"を出力し処理を終了します。
`sum -= aa[left]`を忘れず減算しましょう。

```C++:C++
    rep(left, aa.size()){
        while(right < aa.size() && sum < S){
            sum += aa[right];
            right++;
        }

        if(sum == S){
            cout << "Yes" << endl;
            return 0;
        }
        sum -= aa[left];
    }
```

考察が終わったので実装しましょう。

```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, S;
    cin >> N >> S;
    vector<ll> a(N), aa(N*2);
    rep(i, N) cin >> a[i];
    ll total = 0;
    rep(i, N) total += a[i];
    rep(i, N*2) aa[i] = a[i%N];
    S = S % total;
    if(S == 0){
        cout << "Yes" << endl;
        return 0;
    }

    ll right = 0;
    ll sum = 0;
    rep(left, aa.size()){
        while(right < aa.size() && sum < S){
            sum += aa[right];
            right++;
        }

        if(sum == S){
            cout << "Yes" << endl;
            return 0;
        }
        sum -= aa[left];
    }
    cout << "No" << endl;

    return 0;
} 
```

## [E - Takahashi is Slime 2](https://atcoder.jp/contests/abc384/tasks/abc384_e)

O(HWlogN)
優先度付きキューのbfsの問題です。
スライムが隣接しているマスを毎回探索して、1/X未満か判定するとTLEになります。
隣接するスライムの強さを優先度付きキューに格納して、最も強さの小さいスライムを判定します。

1/X未満か判定する時は、`X - 1`を加算すると簡単に判定できます。

```C++:C++
if(size >= (total + X - 1) / X)
```

高橋くんの強さの初期値を`S[P][Q]`、最初に優先度付きキューへ追加するスライムの強さを`0`にすることでbfsを綺麗に実装することができます。

```C++:C++
    ll total = S[P][Q];
    priority_queue<slime, vector<slime>, Compare> pque;
    pque.emplace(slime(0, Q, P));
    used[P][Q] = true;
```

考察が終わったので実装しましょう。

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

struct slime {
    ll size;
    int x;
    int y;
    slime(ll size_, int x_, int y_) : size(size_), x(x_), y(y_) {}
};

struct Compare {
    bool operator()(const slime& a, const slime& b) {
        return a.size > b.size; 
    }
};

int main() {
    int H, W;
    ll X;
    cin >> H >> W >> X;
    int P, Q;
    cin >> P >> Q;
    P--; Q--;
    vector<vector<ll>> S(H, vector<ll>(W));
    vector<vector<bool>> used(H, vector<bool>(W, false));
    rep(i, H) rep(j, W) cin >> S[i][j];

    ll total = S[P][Q];
    priority_queue<slime, vector<slime>, Compare> pque;
    pque.emplace(slime(0, Q, P));
    used[P][Q] = true;
    
    while(pque.size()){
        const auto [size, x, y] = pque.top();
        pque.pop();

        if(size >= (total + X - 1) / X){
            break;
        }

        total += size;

        for(int i=0; i<4; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];

            if(xx<0 || W<=xx || yy<0 || H<=yy) continue;

            if(used[yy][xx] == false){
                used[yy][xx] = true;
                pque.emplace(slime(S[yy][xx], xx, yy));
            }
        }
    }
    cout << total << endl;

    return 0;
} 
```

このコードを整理しましょう。
自作の構造体を用意しましたが、tupleで十分です。
`Compare`がいらなくなり、`greater<int>()`でソートが可能になります。

```C++:C++
struct slime {
    ll size;
    int x;
    int y;
    slime(ll size_, int x_, int y_) : size(size_), x(x_), y(y_) {}
};

struct Compare {
    bool operator()(const slime& a, const slime& b) {
        return a.size > b.size; 
    }
};
```

以下が修正したコードです。

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

int main() {
    int H, W;
    ll X;
    cin >> H >> W >> X;
    int P, Q;
    cin >> P >> Q;
    P--; Q--;
    vector<vector<ll>> S(H, vector<ll>(W));
    rep(i, H) rep(j, W) cin >> S[i][j];

    ll total = S[P][Q];
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<int>> pque;
    pque.emplace(0, Q, P);
    
    vector<vector<bool>> used(H, vector<bool>(W, false));
    used[P][Q] = true;
    
    while(pque.size()){
        const auto [size, x, y] = pque.top();
        pque.pop();

        if(size >= (total + X - 1) / X){
            break;
        }

        total += size;

        for(int i=0; i<4; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];

            if(xx<0 || W<=xx || yy<0 || H<=yy) continue;

            if(used[yy][xx] == false){
                used[yy][xx] = true;
                pque.emplace(S[yy][xx], xx, yy);
            }
        }
    }
    cout << total << endl;

    return 0;
} 
```