Zenn
🔵

【ABC368】AtCoder Beginner Contest 368【C++】

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

コンテスト名

日立ヴァンタラプログラミングコンテスト2024（AtCoder Beginner Contest 368）

コンテストURL

https://atcoder.jp/contests/abc368

開催日

2024/08/24 21:00-22:40

A: Cut

解法

  1. N - K + 1 番目から N 番目までを出力したあと、 1 番目から N - K 番目までを出力する
  2. rotate() を用いる
ABC368A_1.cpp
#include <iostream>
#include <vector>
using namespace std;

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

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

    for(int i=n-k; i<n; i++){
        if(i!=(n-k)){
            cout << " ";
        }
        cout << A[i];
    }
    for(int i=0; i<n-k; i++){
        cout << " " << A[i];
    }

    cout << endl;
    return 0;
}
ABC368A_2.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

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

    rotate(A.begin(), A.begin()+n-k, A.end());

    for(int i=0; i<n; i++){
        if(i){
            cout << " ";
        }
        cout << A[i];
    }

    cout << endl;
    return 0;
}

B: Decrease 2 max elements

解法

  • 問題文通りにシミュレーションする
ABC368B.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

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

    int cnt = 0;
    sort(A.rbegin(), A.rend());
    while(A[1]>0){
        A[0]--;
        A[1]--;
        sort(A.rbegin(), A.rend());
        cnt++;
    }

    cout << cnt << endl;
    return 0;
}

C: Triple Attack

解法

  • 体力の減少の周期性に着目する
  • T を 3 で割った余りで場合分けする
  • 各敵の体力を 0 以下にするために必要な行動数を O(1) で求める
ABC368C.cpp
#include <iostream>
#include <vector>
using namespace std;

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

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

    long long int t = 0;
    for(int i=0; i<n; i++){
        if(t%3==0){
            t += (H[i]/5)*3;
            if(H[i]%5<=2){
                t += H[i]%5;
            }else{
                t += 3;
            }
        }else if(t%3==1){
            H[i]--;
            t++;
            if(H[i]>0){
                H[i] -= 3;
                t++;
            }
            if(H[i]>0){
                t += (H[i]/5)*3;
                if(H[i]%5<=2){
                    t += H[i]%5;
                }else{
                    t += 3;
                }
            }
        }else if(t%3==2){
            H[i] -= 3;
            t++;
            if(H[i]>0){
                t += (H[i]/5)*3;
                if(H[i]%5<=2){
                    t += H[i]%5;
                }else{
                    t += 3;
                }
            }
        }
    }

    cout << t << endl;
    return 0;
}

D: Minimum Steiner Tree

解法

  1. 頂点 V_1, \cdots, V_K 以外の葉を削除することを繰り返す
  2. 深さ優先探索 (DFS) で各頂点の子のうち、必要な頂点がいくつあるかを数える
ABC368D_1.cpp
#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;

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

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

    set<int> V;
    int v;
    for(int i=0; i<k; i++){
        cin >> v;
        v--;
        V.insert(v);
    }

    if(k==1){
        cout << 1 << endl;
        return 0;
    }

    queue<int> Q;
    for(int i=0; i<n; i++){
        if(G[i].size()==1){
            Q.push(i);
        }
    }

    int cnt = n;
    while(!Q.empty()){
        int now = Q.front();
        Q.pop();

        if(V.count(now)){
            continue;
        }

        int next = *G[now].begin();
        G[now].clear();
        G[next].erase(now);
        cnt--;

        if(G[next].size()==1){
            Q.push(next);
        }
    }

    cout << cnt << endl;

    return 0;
}
ABC368D_2.cpp
#include <iostream>
#include <vector>
#include <set>
using namespace std;

set<int> V;
vector<int> cnt;
vector<vector<int>> G;

void dfs(int now, int p=-1){
    if(V.count(now)){
        cnt[now]++;
    }

    for(int i=0; i<G[now].size(); i++){
        int next = G[now][i];
        if(next==p){
            continue;
        }
        dfs(next, now);
        cnt[now] += cnt[next];
    }
}

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

    G.assign(n, vector<int>());
    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);
    }

    int v;
    for(int i=0; i<k; i++){
        cin >> v;
        v--;
        V.insert(v);
    }

    if(k==1){
        cout << 1 << endl;
        return 0;
    }

    cnt.resize(n);
    dfs(*V.begin());

    int ans = 0;
    for(int i=0; i<n; i++){
        if(cnt[i]){
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}

Discussion