【ABC400】AtCoder Beginner Contest 400【C++】

コンテスト名

AtCoder Beginner Contest 400

コンテストURL

開催日

2025/04/05 21:00-22:40

---

A: ABC400 Party

解法

• $A$ が $400$ の約数ならば、 $400$ を $A$ で割った商が $B$

ABC400A.cpp

#include <iostream>
using namespace std;

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

    if(400%a==0){
        cout << 400 / a << endl;
    }else{
        cout << -1 << endl;
    }

    return 0;
}

B: Sum of Geometric Series

解法

• 総和を順番に計算し、 $10^9$ を超えたら打ち切る

ABC400B.cpp

#include <iostream>
using namespace std;

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

    long long int sum = 0;
    long long int tmp = 1;
    for(int i=0; i<=m; i++){
        sum += tmp;
        if(sum>1000000000){
            cout << "inf" << endl;
            return 0;
        }
        tmp *= n;
    }

    cout << sum << endl;

    return 0;
}

C: 2^a b^2

解法

• $2^a$ を全探索し、各 $a$ において条件を満たす $b$ の数を求める
• 重複がないように、 $b$ は奇数の場合のみを考える
• sqrtl() を使用する

ABC400C.cpp

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

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

    long long int x = 2;
    long long int cnt = 0;
    for(int a=1; a<60; a++){
        long long int y = n / x;
        cnt += (sqrtl(y)+1) / 2;
        x *= 2;
    }

    cout << cnt << endl;

    return 0;
}

D: Takahashi the Wall Breaker

解法

• ダイクストラ法
• 一つ先の区画が道ならば重み $0$ の辺、一つ先の区画が壁ならば重み $1$ の辺を張る
• 二つ先の区画が壁ならば、重み $1$ の辺を張る

ABC400D.cpp

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

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

    vector<string> G(h);
    string s;
    for(int i=0; i<h; i++){
        cin >> s;
        G[i] = s;
    }

    int a, b, c, d;
    cin >> a >> b >> c >> d;
    a--;
    b--;
    c--;
    d--;

    vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
    const int INF = 1e9;
    vector<vector<int>> dist(h, vector<int>(w, INF));
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> Q;
    dist[a][b] = 0;
    Q.emplace(0, a, b);
    while(!Q.empty()){
        auto [c, x, y] = Q.top();
        Q.pop();

        for(int i=0; i<4; i++){
            for(int j=1; j<=2; j++){
                int nx = x + dx[i]*j;
                int ny = y + dy[i]*j;
                if(nx<0 || nx>=h || ny<0 || ny>=w){
                    continue;
                }

                if(G[nx][ny]=='#'){
                    if(dist[nx][ny]>dist[x][y]+1){
                        dist[nx][ny] = dist[x][y] + 1;
                        Q.emplace(dist[nx][ny], nx, ny);
                    }
                }else{
                    if(j==1 && dist[nx][ny]>dist[x][y]){
                        dist[nx][ny] = dist[x][y];
                        Q.emplace(dist[nx][ny], nx, ny);
                    }
                }
            } 
        }
    }

    cout << dist[c][d] << endl;

    return 0;
}