【ABC384】AtCoder Beginner Contest 384【C++】

コンテスト名

トヨタ自動車プログラミングコンテスト2024#12（AtCoder Beginner Contest 384）

コンテストURL

https://atcoder.jp/contests/abc384

開催日

2024/12/14 21:00-22:40

---

A: aaaadaa

解法

• 問題文通りに判定して置き換える

ABC384A.cpp

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

int main(){
    int n;
    char c1, c2;
    cin >> n >> c1 >> c2;
    string s;
    cin >> s;
    for(int i=0; i<n; i++){
        if(s[i]!=c1){
            s[i] = c2;
        }
    }
    cout << s << endl;

    return 0;
}

B: ARC Division

解法

• 問題文通りにシミュレーションする

ABC384B.cpp

#include <iostream>
using namespace std;

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

    int d, a;
    for(int i=0; i<n; i++){
        cin >> d >> a;
        if(d==1){
            if(r>= 1600 && r<=2799){
                r += a;
            }
        }else{
            if(r>= 1200 && r<=2399){
                r += a;
            }
        }
    }

    cout << r << endl;

    return 0;
}

C: Perfect Standings

解法

• bit 全探索
• すべての参加者の点数と名前を bit 全探索で列挙する
• 点数の降順かつ名前の昇順でソートする
  • 点数に $-1$ をかけて vector<pair<int, string>> を昇順にソートする

ABC384C.cpp

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

int main(){
    vector<int> P(5);
    for(int i=0; i<5; i++){
        cin >> P[i];
    }

    string s = "ABCDE";
    vector<pair<int, string>> V;
    for(int i=1; i<(1<<5); i++){
        int sum = 0;
        string t;
        for(int j=0; j<5; j++){
            if(i&(1<<j)){
                t.push_back(s[j]);
                sum += P[j];
            }
        }
        V.emplace_back(-sum, t);
    }

    sort(V.begin(), V.end());
    for(int i=0; i<V.size(); i++){
        auto [point, name] = V[i];
        cout << name << '\n';
    }

    return 0;
}

D: Repeated Sequence

解法

• 累積和と set
• $S$ を $\sum\limits_{i=1}^N A_i$ で割った余り満たすように、数列 $(A_1, A_2, \cdots, A_N)$ の両端からとるイメージ
• 両端からの累積和をそれぞれ set<long long int> に記録しておき、 $S$ を $\sum\limits_{i=1}^N A_i$ で割った余り、もしくは、 $S$ を $\sum\limits_{i=1}^N A_i$ で割った余りに $\sum\limits_{i=1}^N A_i$ を足したものと等しくなるように調整できるかを探索する
• 計算量は $\mathcal{O}(N \log N)$

ABC384D.cpp

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

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

    vector<long long int> V1(n+1), V2(n+1);
    set<long long int> S1, S2;
    S1.insert(0);
    S2.insert(0);
    for(int i=0; i<n; i++){
        V1[i+1] = V1[i] + A[i];
        S1.insert(V1[i+1]);
    }
    for(int i=0; i<n; i++){
        V2[i+1] = V2[i] + A[n-i-1];
        S2.insert(V2[i+1]);
    }

    if(s>=sum){
        s %= sum;
        for(int i=0; i<n; i++){
            if(S2.count(s-V1[i+1])){
                cout << "Yes" << endl;
                return 0;
            }
        }
        for(int i=0; i<n; i++){
            if(S1.count(s-V2[i+1])){
                cout << "Yes" << endl;
                return 0;
            }
        }
        s += sum;
        for(int i=0; i<n; i++){
            if(S2.count(s-V1[i+1])){
                cout << "Yes" << endl;
                return 0;
            }
        }
        for(int i=0; i<n; i++){
            if(S1.count(s-V2[i+1])){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }else{
        for(int i=0; i<n; i++){
            if(S1.count(V1[i+1]-s)){
                cout << "Yes" << endl;
                return 0;
            }
        }
        for(int i=0; i<n; i++){
            if(S2.count(V2[i+1]-s)){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;

    return 0;
}

E: Takahashi is Slime 2

解法

• 優先度付きキューを使った幅優先探索 (BFS)
• 隣接するスライムのうち、強さが最も小さいスライムを吸収することを繰り返す
• priority_queue<tuple<long long int, int, int> に強さと位置を記録する

ABC384E.cpp

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

int main(){
    int h, w, b;
    cin >> h >> w >> b;
    int p, q;
    cin >> p >> q;
    p--;
    q--;

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

    priority_queue<tuple<long long int, int, int>, vector<tuple<long long int, int, int>>, greater<tuple<long long int, int, int>>> Q;
    vector<vector<int>> seen(h, vector<int>(w));
    Q.emplace(-1, p, q);
    seen[p][q] = 1;
    long long int now = S[p][q];
    vector<int> dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
    while(!Q.empty()){
        auto [num, x, y] = Q.top();
        Q.pop();
        
        if(S[x][y]<(now+b-1)/b){
            now += S[x][y];
        }
        if(num>=(now+b-1)/b){
            break;
        }

        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(seen[nx][ny]){
                continue;
            }
            
            Q.emplace(S[nx][ny], nx, ny);
            seen[nx][ny] = 1;
        }
    }

    cout << now << endl;

    return 0;
}