【ABC433】AtCoder Beginner Contest 433【C++】

コンテスト名

AtCoder Beginner Contest 433

コンテストURL

https://atcoder.jp/contests/abc433

開催日

2025/11/22 21:00–22:40

---

A: Happy Birthday! 4

解法

• $1$ 年ごとにシミュレーションする

ABC433A.cpp

#include <iostream>
using namespace std;

int main(){
    int x, y, z;
    cin >> x >> y >> z;

    for(int i=0; i<=100; i++){
        if((x+i)==(y+i)*z){
            cout << "Yes" << endl;
            return 0;
        }
    }

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

B: Nearest Taller

解法

• 問題文通りに探索して判定する

ABC433B.cpp

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

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

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

    vector<int> V(n, -1);
    for(int i=0; i<n; i++){
        for(int j=0; j<i; j++){
            if(A[j]>A[i]){
                V[i] = j + 1;
            }
        }
    }

    for(int i=0; i<n; i++){
        cout << V[i] << '\n';
    }

    return 0;
}

C: 1122 Substring 2

解法

• 条件を満たす箇所を発見し次第、前後に探索することを繰り返す

ABC433C.cpp

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

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

    int n = s.size();
    int cnt = 0;
    for(int i=0; i<n-1; i++){
        if((s[i]-'0')+1!=(s[i+1]-'0')){
            continue;
        }

        int left = i, right = i+1;
        int lnum = (s[i]-'0'), rnum = (s[i+1]-'0');
        while(left>=0 && right<=n-1){
            if((s[left]-'0')==lnum && (s[right]-'0')==rnum){
                cnt++;
                left--;
                right++;
            }else{
                break;
            }
        }
    }

    cout << cnt << endl;

    return 0;
}

D: 183183

解法

• $f(A_i, A_j) = {A_i} \times 10^{\mathrm{len}(A_j)} + A_j$
• $f(A_i, A_j)$ を $M$ で割った余りは、 $({A_i} \times 10^{\mathrm{len}(A_j)} \bmod M) + (A_j \bmod M)$
• vector<unordered_map<int, int>> に繰り上がる桁（ $\mathrm{len}(A_j)$ ）ごとの $M$ で割った余り（ $({A_i} \times 10^{\mathrm{len}(A_j)} \bmod M)$ ）別の個数を記録する
• $M$ で割った余りが $0$ になる組み合わせを考える

ABC433D.cpp

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

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

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

    vector<unordered_map<int, int>> V(11);
    for(int i=0; i<n; i++){
        V[0][A[i]%m]++;
        long long int a = A[i] % m;
        for(int j=1; j<=10; j++){
            a *= 10;
            a %= m;
            V[j][a]++;
        }
    }

    long long int cnt = 0;
    for(int i=0; i<n; i++){
        string s = to_string(A[i]);
        int len = s.size();

        cnt += V[len][(m-(A[i]%m))%m];
    }

    cout << cnt << endl;

    return 0;
}