【ABC425】AtCoder Beginner Contest 425【C++】

コンテスト名

ユニークビジョンプログラミングコンテスト2025 秋（AtCoder Beginner Contest 425）

コンテストURL

https://atcoder.jp/contests/abc425

開催日

2025/09/27 21:00–22:40

---

A: Sigma Cubes

解法

• 問題文通りに計算する

ABC425A.cpp

#include <iostream>
using namespace std;

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

    int ans = 0;
    for(int i=1; i<=n; i++){
        int sum = 1;
        if(i%2!=0){
            sum *= -1;
        }
        for(int j=0; j<3; j++){
            sum *= i;
        }
        ans += sum;
    }

    cout << ans << endl;

    return 0;
}

B: Find Permutation 2

解法

• 順列全探索

ABC425B.cpp

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

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

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

    do{
        bool flag = true;
        for(int i=0; i<n; i++){
            if(A[i]==-1){
                continue;
            }

            if(A[i]!=P[i]){
                flag = false;
                break;
            }
        }

        if(flag){
            cout << "Yes" << endl;
            for(int i=0; i<n; i++){
                if(i){
                    cout << " ";
                }
                cout << P[i];
            }
            cout << endl;
            return 0;
        }
    }while(next_permutation(P.begin(), P.end()));

    cout << "No" << endl;

    return 0;
}

C: Rotate and Sum Query

解法

• 累積和
• 長さ $2N$ の数列をつくって、周をまたぐ場合に対応する

ABC425C.cpp

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

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

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

    vector<long long int> S(n*2+1);
    for(int i=0; i<2*n; i++){
        S[i+1] += A[i] + S[i];
    }

    int top = 0;
    int num, c, l, r;
    while(q--){
        cin >> num;

        if(num==1){
            cin >> c;
            top += c;
            top %= n;
        }else if(num==2){
            cin >> l >> r;
            l--;
            r--;

            cout << S[top+r+1] - S[top+l] << '\n';
        }
    }

    return 0;
}

D: Ulam-Warburton Automaton

解法

• 幅優先探索 (BFS)
• 各回でマスを黒で塗る操作は同時に実行されることに注意する

ABC425D.cpp

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

int main(){
    int h, w;
    cin >> h >> w;

    vector<vector<char>> G(h, vector<char>(w));
    queue<pair<int, int>> Q;
    int ans = 0;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> G[i][j];
            if(G[i][j]=='#'){
                Q.emplace(i, j);
                ans++;
            }
        }
    }

    vector<int> dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
    while(true){
        set<pair<int, int>> S;
        queue<pair<int, int>> TQ = Q;
        while(!Q.empty()){
            Q.pop();
        }

        while(!TQ.empty()){
            auto [x, y] = TQ.front();
            TQ.pop();

            for(int i=0; i<4; i++){
                int nx = x + dx[i], ny = y + dy[i];

                if(nx<0 || nx>=h || ny<0 || ny>=w){
                    continue;
                }

                if(G[nx][ny]=='.'){
                    S.emplace(nx, ny);
                }
            }
        }

        vector<pair<int, int>> V;
        for(auto [nx, ny] : S){
            int cnt = 0;
            for(int j=0; j<4; j++){
                int nnx = nx + dx[j], nny = ny + dy[j];

                if(nnx<0 || nnx>=h || nny<0 || nny>=w){
                    continue;
                }

                if(G[nnx][nny]=='#'){
                    cnt++;
                }
            }

            if(cnt==1){
                V.emplace_back(nx, ny);
            }
        }

        if(V.empty()){
            break;
        }

        for(auto [nx, ny] : V){
            G[nx][ny] = '#';
            Q.emplace(nx, ny);
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}