0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

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

Posted at

コンテスト名

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

コンテストURL

開催日

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;
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?