Zenn
🔵

【ABC348】AtCoder Beginner Contest 348【C++】

2024/04/07に公開
C++
#
競技プログラミング
AtCoder
アルゴリズム
tech

コンテスト名

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

コンテストURL

https://atcoder.jp/contests/abc348

開催日

2024/04/06 21:00-22:40

A: Penalty Kick

解法

  • 問題文通りに実装する
ABC348A.cpp
#include <iostream>
using namespace std;

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

    for(int i=1; i<=n; i++){
        if(i%3==0){
            cout << "x";
        }else{
            cout << "o";
        }
    }

    cout << endl;
    return 0;
}

B: Farthest Point

解法

  • 全探索
  • pow() などで小数を用いると誤差が出るのでユークリッド距離の二乗でそのまま計算
  • 最大値が更新されたら点の番号も更新する
ABC348B.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> X(n), Y(n);
    for(int i=0; i<n; i++){
        cin >> X[i] >> Y[i];
    }

    vector<int> ans(n);
    for(int i=0; i<n; i++){
        int maxv = 0;
        int num = -1;
        for(int j=0; j<n; j++){
            int dist = (X[i]-X[j])*(X[i]-X[j]) + (Y[i]-Y[j])*(Y[i]-Y[j]);
            if(dist>maxv){
                maxv = dist;
                num = j+1;
            }
        }
        ans[i] = num;
    }

    for(int i=0; i<n; i++){
        cout << ans[i] << '\n';
    }

    return 0;
}

C: Colorful Beans

解法

  • 各色の「おいしさ」の最小値を unordered_map<int, int> で管理する
  • 「おいしさ」の最小値が最大の色の「おいしさ」を出力する
ABC348C.cpp
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

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

    unordered_map<int, int> M;
    int a, c;
    for(int i=0; i<n; i++){
        cin >> a >> c;
        if(!M.count(c)){
            M[c] = a;
        }else if(a<M[c]){
            M[c] = a;
        }
    }

    int maxv = 0;
    for(auto p : M){
        maxv = max(maxv, p.second);
    }

    cout << maxv << endl;
    return 0;
}

D: Medicines on Grid

解法

  • 幅優先探索 (BFS)
  • 各マスのエネルギー残量の最大値を vector<vector<int>> で記録しながら幅優先探索
  • 各マスで記録していたエネルギー残量よりも大きなエネルギー残量が可能であることが判明したら更新する
    • vector<vector<int>> を更新して当該マスを queue<pair<int, int>> にプッシュする
  • 幅優先探索終了後の vector<vector<int>> には各マスについてありうる最大のエネルギー残量が記録されている
  • 「ゴール地点」のエネルギー残量が 0 以上なら移動可能
  • （「薬」を使う回数の最小値を求める問題の場合）
    • 「薬」があるマスを頂点としたグラフを考えて「薬 i 」から「薬 j 」まで移動できるかを幅優先探索で記録する（辺を張る）
    • 「薬」があるマスを頂点としたグラフにおいて「スタート地点」を始点として「ゴール地点」までの距離を幅優先探索で求める
ABC348D.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

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

    vector<vector<int>> G(h, vector<int>(w));
    char a;
    int sx, sy, tx, ty;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> a;
            if(a=='#'){
                G[i][j] = -1;
            }else if(a=='S'){
                sx = i;
                sy = j;
            }else if(a=='T'){
                tx = i;
                ty = j;
            }
        }
    }

    int n;
    cin >> n;
    int r, c, e;
    for(int i=0; i<n; i++){
        cin >> r >> c >> e;
        r--;
        c--;
        G[r][c] = e;
    }

    vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
    queue<pair<int, int>> Q;
    vector<vector<int>> energy(h, vector<int>(w, -1));
    Q.emplace(sx, sy);
    energy[sx][sy] = G[sx][sy];
    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-1 || ny<0 || ny>w-1){
                continue;
            }
            if(G[nx][ny]==-1 || energy[x][y]<1){
                continue;
            }

            if(energy[nx][ny]<G[nx][ny] || energy[nx][ny]<energy[x][y]-1){
                energy[nx][ny] = max(G[nx][ny], energy[x][y] - 1);
                Q.emplace(nx, ny);
            }
        }
    }

    if(energy[tx][ty]>=0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

E: Minimize Sum of Distances

解法

  • 頂点 i の重みが C_i の木の重心を考える
    • f(x) は頂点 x が重心であるときに最小になる
  • 頂点 v が重心であるとき頂点 v に連なる各部分木について重みの総和はそれぞれ当該部分木以外の重みの総和（全体 - 各部分木）以下である
ABC348E.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    vector<vector<int>> G(n);
    int a, b;
    for(int i=0; i<n-1; i++){
        cin >> a >> b;
        a--;
        b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

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

    int center;
    auto dfs = [&](auto dfs, int v, int p=-1) -> long long int {
        long long int res = C[v];
        long long int maxv = 0;
        for(int i=0; i<G[v].size(); i++){
            if(G[v][i]==p){
                continue;
            }
            long long int child = dfs(dfs, G[v][i], v);
            maxv = max(maxv, child);
            res += child;
        }
        maxv = max(maxv, sum-res);
        if(maxv<=sum-maxv){
            center = v;
        }
        return res;
    };
    dfs(dfs, 0);

    long long int ans = 0;
    auto dfs2 = [&](auto dfs2, int v, int dist=0, int p=-1) -> void {
        ans += (long long int)dist*C[v];
        for(int i=0; i<G[v].size(); i++){
            if(G[v][i]==p){
                continue;
            }
            dfs2(dfs2, G[v][i], dist+1, v);
        }
    };
    dfs2(dfs2, center);

    cout << ans << endl;
    return 0;
}

Discussion