【ABC387】AtCoder Beginner Contest 387【C++】

コンテスト名

AtCoder Beginner Contest 387（Promotion of AtCoderJobs）

コンテストURL

開催日

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

---

A: Happy New Year 2025

解法

• 問題文通りに計算する

ABC387A.cpp

#include <iostream>
using namespace std;

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

    cout << (a+b)*(a+b) << endl;

    return 0;
}

B: 9x9 Sum

解法

• 全探索する

ABC387B.cpp

#include <iostream>
using namespace std;

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

    int sum = 0;
    for(int i=1; i<=9; i++){
        for(int j=1; j<=9; j++){
            if(i*j!=x){
                sum += i*j;
            }
        }
    }

    cout << sum << endl;

    return 0;
}

C: Snake Numbers

解法

• $f(X)$ を $X$ 以下のヘビ数の数を求める関数とする
• $X$ より桁数が小さいもの、 $X$ と同じ桁数のものについて、順にヘビ数の数を求めていく
• 答えは、 $f(R) - f(L-1)$ で求められる

ABC387C.cpp

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

long long int pow_calc(long long int x, int t){
    if(t==0){
        return 1;
    }

    if(t%2==1){
        return x*pow_calc(x, t-1);
    }else{
        long long int a = pow_calc(x, t/2);
        return a*a;
    }
}

long long int f(long long int x){
    if(x<10){
        return 0;
    }

    string s = to_string(x);
    int keta = s.size();
    int top = s[0] - '0';
    long long int res = 0;

    for(int i=2; i<keta; i++){
        for(int j=1; j<=9; j++){
            res += pow_calc(j, i-1);
        }
    }

    for(int i=1; i<top; i++){
        res += pow_calc(i, keta-1);
    }

    bool flag = false;
    for(int i=1; i<keta; i++){
        flag = true;
        for(int j=0; j<top; j++){
            if(j==s[i]-'0'){
                flag = false;
                break;
            }
            res += pow_calc(top, keta-i-1);
        }
        if(flag){
            break;
        }
    }
    if(!flag){
        res += 1;
    }

    return res;
}

int main(){
    long long int l, r;
    cin >> l >> r;
    
    cout << f(r) - f(l-1) << endl;

    return 0;
}

D: Snaky Walk

解法

• 幅優先探索 (BFS)
• 縦移動と横移動をそれぞれ記録しながら幅優先探索する

ABC387D.cpp

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

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

    vector<vector<char>> G(h, vector<char>(w));
    char c;
    int sx, sy, gx, gy;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> c;
            G[i][j] = c;
            if(c=='S'){
                sx = i;
                sy = j;
            }else if(c=='G'){
                gx = i;
                gy = j;
            }
        }
    }

    vector<int> dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
    queue<tuple<int, int, int>> Q;
    vector<vector<vector<int>>> dist(2, vector<vector<int>>(h, vector<int>(w, -1)));
    Q.emplace(sx, sy, 2);
    dist[0][sx][sy] = 0;
    dist[1][sx][sy] = 0;
    while(!Q.empty()){
        auto [x, y, d] = Q.front();
        Q.pop();

        for(int i=0; i<4; i++){
            if(d==0){
                if(i%2==0){
                    continue;
                }
            }else if(d==1){
                if(i%2!=0){
                    continue;
                }
            }

            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx<0 || nx>=h || ny<0 || ny>=w){
                continue;
            }
            if(dist[i%2][nx][ny]!=-1 || G[nx][ny]=='#'){
                continue;
            }

            dist[i%2][nx][ny] = dist[(i+1)%2][x][y] + 1;
            Q.emplace(nx, ny, i%2);
        }
    }

    if(dist[0][gx][gy]==-1 && dist[1][gx][gy]==-1){
        cout << -1 << endl;
    }else if(dist[0][gx][gy]!=-1 && dist[1][gx][gy]!=-1){
        cout << min(dist[0][gx][gy], dist[1][gx][gy]) << endl;
    }else{
        cout << max(dist[0][gx][gy], dist[1][gx][gy]) << endl;
    }

    return 0;
}