【ABC409】AtCoder Beginner Contest 409【C++】

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

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

### 開催日
2025/06/07 21:00–22:40

---

## [A: Conflict](https://atcoder.jp/contests/abc409/tasks/abc409_a)
**解法**
- 問題文通りに判定する
```cpp:ABC409A.cpp
#include <iostream>
#include <string>
using namespace std;

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

    string t, a;
    cin >> t >> a;

    for(int i=0; i<n; i++){
        if(t[i]=='o' && a[i]=='o'){
            cout << "Yes" << endl;
            return 0;
        }
    }

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

## [B: Citation](https://atcoder.jp/contests/abc409/tasks/abc409_b)
**解法**
- 昇順にソートしてから、 $x$ が答えとなるには、 $A_{N-x+1}$ が $x$ 以上でなければならないことによって判定する
```cpp:ABC409B.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

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

    sort(A.begin(), A.end());
    for(int i=n; i>0; i--){
        if(A[n-i]>=i){
            cout << i << endl;
            return 0;
        }
    }

    cout << 0 << endl;

    return 0;
}
```

## [C: Equilateral Triangle](https://atcoder.jp/contests/abc409/tasks/abc409_c)
**解法**
- $L$ が $3$ で割り切れないときは、正三角形をつくれない
- 等間隔（差 $\frac{L}{3}$）で並ぶ $3$ 点の組み合わせの数を求める
- 組み合わせを数えるとき、重複に注意する
```cpp:ABC409C.cpp
#include <iostream>
#include <vector>
using namespace std;

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

    vector<int> D(n-1);
    for(int i=0; i<n-1; i++){
        cin >> D[i];
    }

    if(l%3!=0){
        cout << 0 << endl;
        return 0;
    }

    vector<int> V(n);
    vector<long long int> C(l);
    C[0]++;
    for(int i=0; i<n-1; i++){
        V[i+1] += V[i] + D[i];
        V[i+1] %= l;
        C[V[i+1]]++;
    }

    long long int cnt = 0;
    int l3 = l / 3;
    for(int i=0; i<l3; i++){
        cnt += C[i] * C[i+l3] * C[i+l3*2];
    }

    cout << cnt << endl;

    return 0;
}
```

## [D: String Rotation](https://atcoder.jp/contests/abc409/tasks/abc409_d)
**解法**
- 文字列を左から見ていき、最初に $S_{i} > S_{i+1}$ となった位置で操作を実行するのが最適である
- 最初に $S_{i} > S_{i+1}$ となったときの $S_{i}$ を、最初に $S_{i} < S_{j}$ となる位置に挿入する
    - このとき、 $l = i, \ r = j-1$
- 計算量は $\mathrm{O}(N)$
```cpp:ABC409D.cpp
#include <iostream>
#include <string>
using namespace std;

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

    while(t--){
        int n;
        cin >> n;

        string s;
        cin >> s;

        string ans = "";
        bool flag = true;
        int i;
        for(i=0; i<n-1; i++){
            if((s[i+1]-'a')<(s[i]-'a')){
                flag = false;
                
                int j;
                for(j=i+1; j<n; j++){
                    if((s[j]-'a')<=(s[i]-'a')){
                        ans.push_back(s[j]);
                    }else{
                        break;
                    }
                }

                ans.push_back(s[i]);

                for(int k=j; k<n; k++){
                    ans.push_back(s[k]);
                }

                break;
            }else{
                ans.push_back(s[i]);
            }
        }

        if(flag){
            ans.push_back(s.back());
        }

        cout << ans << '\n';
    }

    return 0;
}
```