【ABC383】AtCoder Beginner Contest 383【C++】

コンテスト名

大和証券プログラミングコンテスト2024（AtCoder Beginner Contest 383）

コンテストURL

https://atcoder.jp/contests/abc383

開催日

2024/12/07 21:00:22:40

---

A: Humidifier 1

解法

• 問題文通りにシミュレーションする
• 加湿器に残っている水の量は負の値にはならないことに注意する

ABC383A.cpp

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

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

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

    int ans = V[0];
    for(int i=0; i<n-1; i++){
        ans -= min(ans, T[i+1]-T[i]);
        ans += V[i+1];
    }

    cout << ans << endl;

    return 0;
}

B: Humidifier 2

解法

• 全探索
• 加湿器を置くマスを全探索して、加湿される床のマスの個数を毎回数える
• 計算量は $\mathcal{O}((HW)^3)$

ABC383B.cpp

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

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

    vector<vector<char>> S(h, vector<char>(w));
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> S[i][j];
        }
    }

    int maxv = 0;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            for(int k=0; k<h; k++){
                for(int l=0; l<w; l++){
                    if(i==k && j==l){
                        continue;
                    }
                    if(S[i][j]!='.' || S[k][l]!='.'){
                        continue;
                    }

                    vector<vector<int>> G(h, vector<int>(w));
                    for(int a=0; a<h; a++){
                        for(int b=0; b<w; b++){
                            int x = abs(i-a) + abs(j-b);
                            int y = abs(k-a) + abs(l-b);
                            if(x<=d || y<=d){
                                G[a][b] = 1;
                            }
                        }
                    }

                    int cnt = 0;
                    for(int a=0; a<h; a++){
                        for(int b=0; b<w; b++){
                            if(G[a][b] && S[a][b]=='.'){
                                cnt++;
                            }
                        }
                    }

                    maxv = max(maxv, cnt);
                }
            }
        }
    }

    cout << maxv << endl;

    return 0;
}

C: Humidifier 3

解法

• 多始点幅優先探索 (BFS)
• 最初に、加湿器が置かれた床のマスすべてを queue<pair<int, int>> にプッシュしておく
• 全始点から同時に探索が始まるイメージ

ABC383C.cpp

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

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

    vector<vector<char>> S(h, vector<char>(w));
    vector<vector<int>> dist(h, vector<int>(w, d+1));
    queue<pair<int, int>> Q;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> S[i][j];
            if(S[i][j]=='H'){
                dist[i][j] = 0;
                Q.emplace(i, j);
            }
        }
    }

    
    vector<int> dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
    while(!Q.empty()){
        auto [x, y] = Q.front();
        Q.pop();

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx<0 || nx>=h || ny<0 || ny>=w){
                continue;
            }
            if(S[nx][ny]=='#'){
                continue;
            }

            int c = dist[x][y] + 1;
            if(c>=dist[nx][ny]){
                continue;
            }
            dist[nx][ny] = c;
            Q.emplace(nx, ny);
        }
    }

    int cnt = 0;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if(dist[i][j]<=d){
                cnt++;
            }
        }
    }

    cout << cnt << endl;

    return 0;
}

D: 9 Divisors

解法

• 約数の個数の公式を用いる
  • 正の整数 $X$ が $X = p^a \times q^b$ と素因数分解されるとき、 $X$ の正の約数の個数は $(a + 1)(b + 1)$ で表される
  • $p, q$ が素数であることに注意する
• 正の約数をちょうど $9$ 個もつ正の整数は、 $p^8$ もしくは $p^2 q^2$ で表される
• $p^8 \leqq N$ もしくは $p^2 q^2 \leqq N$ を満たす素数 $p, q$ を探索する

ABC383D.cpp

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

bool is_prime(long long int n){
    for(long long int i=2; i*i<=n; i++) {
        if(n%i==0){
            return false;
        }
    }
    return true;
}

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

    long long int sn = ceil(pow(n, 0.5));
    set<long long int> S;
    for(long long int i=2; i<n; i++){
        long long int x = pow(i, 8);
        if(x>n){
            break;
        }else if(is_prime(i)){
            S.insert(x);
        }
    }

    for(long long int i=2; i<n; i++){
        long long int x = i*i;
        if(x>sn){
            break;
        }
        if(!is_prime(i)){
            continue;
        }
        for(long long int j=i+1; j<n; j++){
            long long int y = j*j;
            if(y>n || x*y>n){
                break;
            }
            if(is_prime(j)){
                S.insert(x*y);
            }
        }
    }

    cout << S.size() << endl;

    return 0;
}