【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

解法

• 問題文通りに判定する

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

解法

• 昇順にソートしてから、 $x$ が答えとなるには、 $A_{N-x+1}$ が $x$ 以上でなければならないことによって判定する

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

解法

• $L$ が $3$ で割り切れないときは、正三角形をつくれない
• 等間隔（差 $\frac{L}{3}$）で並ぶ $3$ 点の組み合わせの数を求める
• 組み合わせを数えるとき、重複に注意する

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

解法

• 文字列を左から見ていき、最初に $S_{i} > S_{i+1}$ となった位置で操作を実行するのが最適である
• 最初に $S_{i} > S_{i+1}$ となったときの $S_{i}$ を、最初に $S_{i} < S_{j}$ となる位置に挿入する
  • このとき、 $l = i, \ r = j-1$
• 計算量は $\mathrm{O}(N)$

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