【ABC414】AtCoder Beginner Contest 414【C++】

コンテスト名

ミラティブ プログラミングコンテスト2025（AtCoder Beginner Contest 414）

コンテストURL

https://atcoder.jp/contests/abc414

開催日

2025/07/12 21:00–22:40

---

A: Streamer Takahashi

解法

• 問題文通りに判定する

ABC414A.cpp

#include <iostream>
using namespace std;

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

    int cnt = 0;
    int x, y;
    for(int i=0; i<n; i++){
        cin >> x >> y;

        if(x<=l && y>=r){
            cnt++;
        }
    }

    cout << cnt << endl;

    return 0;
}

B: String Too Long

解法

• オーバーフローに注意して判定する

ABC414B.cpp

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

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

    char c;
    long long int l;
    vector<pair<char, long long int>> V;
    bool flag = true;
    for(int i=0; i<n; i++){
        cin >> c >> l;
        if(l>100){
            flag = false;
        }
        V.emplace_back(c, l);
    }

    if(flag){
        int sum = 0;
        for(int i=0; i<n; i++){
            sum += V[i].second;
        }
        if(sum>100){
            flag = false;
        }
    }

    if(flag){
        string ans = "";
        for(int i=0; i<n; i++){
            for(int j=0; j<V[i].second; j++){
                ans += V[i].first;
            }
        }
        cout << ans << endl;
    }else{
        cout << "Too Long" << endl;
    }

    return 0;
}

C: Palindromic in Both Bases

解法

• $10$ 進数における回文数を全列挙して、 $A$ 進数でも回文であるかを判定する
• 回文数は前半部分だけを考えて、後半は反転して結合させればよい

ABC414C.cpp

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

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

    vector<long long int> V;
    for(int i=1; i<=9; i++){
        if(i<=n){
            V.push_back(i);
        }
    }
    for(int i=1; i<1000000; i++){
        string s = to_string(i);
        string t = s;
        reverse(t.begin(), t.end());

        long long int x = stoll(s + t);
        if(x<=n){
            V.push_back(x);
        }
        
        for(int j=0; j<=9; j++){
            x = stoll(s + to_string(j) + t);
            if(x<=n){
                V.push_back(x);
            }
        }
    }

    long long int sum = 0;
    for(int i=0; i<V.size(); i++){
        long long int x = V[i];
        long long int tmp = x;
        vector<int> N;
        while(x>0){
            N.push_back(x%a);
            x /= a;
        }

        bool flag = true;
        for(int j=0; j<N.size(); j++){
            if(N[j]!=N[N.size()-1-j]){
                flag = false;
                break;
            }
        }

        if(flag){
            sum += tmp;
        }
    }

    cout << sum << endl;

    return 0;
}

D: Transmission Mission

解法

• 隣り合う家の座標の差の総和から、隣り合う家の座標の差の上位 $M - 1$ つの総和を引いた値が答えである
  • 隣り合う家の座標の差を降順にソートしたときの前から $M - 1$ つの区間には、電波が届かなくてもよいため

ABC414D.cpp

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

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

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

    sort(X.begin(), X.end());
    vector<long long int> D;
    long long int sum = 0;
    for(int i=0; i<n-1; i++){
        D.push_back(X[i+1]-X[i]);
        sum += (X[i+1] - X[i]);
    }

    sort(D.rbegin(), D.rend());
    for(int i=0; i<m-1; i++){
        sum -= D[i];
    }

    cout << sum << endl;

    return 0;
}