【ABC429】AtCoder Beginner Contest 429【C++】

コンテスト名

Polaris.AI プログラミングコンテスト 2025（AtCoder Beginner Contest 429）

コンテストURL

開催日

2025/10/25 21:00–22:40

---

A: Too Many Requests

解法

• 問題文通りに判定する

ABC429A.cpp

#include <iostream>
using namespace std;

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

    for(int i=1; i<=n; i++){
        if(i<=m){
            cout << "OK" << '\n';
        }else{
            cout << "Too Many Requests" << '\n';
        }
    }

    return 0;
}

B: N - 1

解法

• 総和から $A_i$ を引いた数と $M$ を比較する

ABC429B.cpp

#include <iostream>
#include <vector>
using namespace std;

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

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

    for(int i=0; i<n; i++){
        if(sum-A[i]==m){
            cout << "Yes" << endl;
            return 0;
        }
    }

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

C: Odd One Subsequence

解法

• 各整数の個数を map<int, long long int> に記録する
• $2$ つの選び方と、残りの $1$ つの選び方を組み合わせとして計算で求める

ABC429C.cpp

#include <iostream>
#include <map>
using namespace std;

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

    int a;
    map<int, long long int> M;
    for(int i=0; i<n; i++){
        cin >> a;
        M[a]++;
    }

    int m = M.size();
    long long int sum = 0;
    for(auto [num, cnt] : M){
        if(cnt>=2){
            sum += ((cnt * (cnt - 1)) / 2) * (n - cnt);
        }
    }

    cout << sum << endl;

    return 0;
}

D: On AtCoder Conference

解法

• 累積和と二分探索
• 同じ区間に位置する地点の $X_i$ はすべて等しいことに着目する

ABC429D.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int main(){
    long long int n, m, c;
    cin >> n >> m >> c;

    map<long long int, int> M;
    long long int a;
    for(int i=0; i<n; i++){
        cin >> a;
        M[a]++;
    }

    vector<pair<long long int, int>> V;
    int sum = 0;
    for(auto [idx, cnt] : M){
        sum += cnt;

        V.emplace_back(idx, sum);
    }

    vector<pair<long long int, int>> V2 = V;
    for(int i=0; i<V.size(); i++){
        V2.emplace_back(V[i].first + m, V[i].second + n);
    }

    vector<int> S;
    for(int i=0; i<V2.size(); i++){
        S.push_back(V2[i].second);
    }

    long long int ans = 0;
    for(int i=0; i<V.size(); i++){
        int x = 0;
        if(i){
            x = V[i-1].second;
        }

        int sum2 = x + c;

        int idx = lower_bound(S.begin()+i, S.end(), sum2) - S.begin();

        int y = V2[idx].second - x;

        long long int len;
        if(i){
            len = V[i].first - V[i-1].first;
        }else{
            len = (m - V.back().first) + V[0].first;
        }

        ans += len * y;
    }

    cout << ans << endl;

    return 0;
}