【ABC360】AtCoder Beginner Contest 360【C++】

### コンテスト名
AtCoder Beginner Contest 360

### コンテストURL
https://atcoder.jp/contests/abc360

### 開催日
2024/06/30 21:00-22:40

---

## [A: A Healthy Breakfast](https://atcoder.jp/contests/abc360/tasks/abc360_a)
**解法**
- `R` か `M` が来たら答えを出力してプログラムを終了する
    - `R` が先に来たら `Yes` を出力してプログラムを終了する
    - `M` が先に来たら `No` を出力してプログラムを終了する
```cpp:ABC360A.cpp
#include <iostream>
#include <string>
using namespace std;

int main(){
    string s;
    cin >> s;

    for(int i=0; i<s.size(); i++){
        if(s[i]=='M'){
            cout << "No" << endl;
            return 0;
        }else if(s[i]=='R'){
            cout << "Yes" << endl;
            return 0;
        }
    }
}
```

## [B: Vertical Reading](https://atcoder.jp/contests/abc360/tasks/abc360_b)
**解法**
- $w$ と $c$ を全探索する
- $\text{S} [i \times w + c] = \text{T} [i]$ がすべての $i$ について成り立つ $w$ と $c$ を全探索する
```cpp:ABC360B.cpp
#include <iostream>
#include <string>
using namespace std;

int main(){
    string s, t;
    cin >> s >> t;

    for(int w=1; w<s.size(); w++){
        for(int c=1; c<=w; c++){
            bool flag = true;
            int i;
            for(i=0; i*w+c-1<s.size(); i++){
                if(i>=t.size()){
                    flag = false;
                    break;
                }
                if(s[i*w+c-1]!=t[i]){
                    flag = false;
                    break;
                }
            }

            if(flag && i==t.size()){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;
    return 0;
}
```

## [C: Move It](https://atcoder.jp/contests/abc360/tasks/abc360_c)
**解法**
- 箱に入っている荷物のうち、最も重い荷物以外を移動させるのが最適である
- `vector<vector<int>>` で各箱に入っている荷物を管理する
- 各箱の荷物を重さの昇順にソートして、最も重い荷物以外の重さを加算する
- 荷物が入っていない箱の `size()` に注意する
```cpp:ABC360C.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    vector<int> A(n), W(n);
    for(int i=0; i<n; i++){
        cin >> A[i];
        A[i]--;
    }
    for(int i=0; i<n; i++){
        cin >> W[i];
    }

    vector<vector<int>> B(n);
    for(int i=0; i<n; i++){
        B[A[i]].push_back(W[i]);
    }

    int sum = 0;
    for(int i=0; i<n; i++){
        if(B[i].size()>0){
            sort(B[i].begin(), B[i].end());
            for(int j=0; j<B[i].size()-1; j++){
                sum += B[i][j];
            }
        }
    }

    cout << sum << endl;
    return 0;
}
```

## [D: Ghost Ants](https://atcoder.jp/contests/abc360/tasks/abc360_d)
**解法**
- 二分探索
- 負の方向を向いている蟻 $A_{0i}$ とすれ違うのは、正の方向を向いている蟻のうち、蟻 $A_{0i}$ よりも負の方向にいて、蟻 $A_{0i}$ との距離が $2T$ 以下の蟻である
- 負の方向を向いている蟻 $A_{0i}$ と正の方向を向いている蟻 $A_{1j}$ がすれ違う条件は、 $X_i - 2T \leqq X_j < X_i$
- 条件を満たす蟻 $A_{1j}$ の数を各蟻 $A_{0i}$ について求める
- $- 2T$ によってオーバーフローすることがあるため、`long long int` にする必要があることに注意する
```cpp:ABC360D.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n, t;
    cin >> n >> t;

    string s;
    cin >> s;

    int x;
    vector<long long int> V0, V1;
    for(int i=0; i<n; i++){
        cin >> x;
        if(s[i]=='0'){
            V0.push_back(x);
        }else{
            V1.push_back(x);
        }
    }

    sort(V1.begin(), V1.end());
    long long int cnt = 0;
    for(int i=0; i<V0.size(); i++){
        cnt += upper_bound(V1.begin(), V1.end(), V0[i]) - lower_bound(V1.begin(), V1.end(), V0[i]-2*t);
    }

    cout << cnt << endl;
    return 0;
}
```