日立ヴァンタラプログラミングコンテスト2024（AtCoder Beginner Contest 368）に参加しました。

使用しているテンプレート

A - Cut

後ろ $K$ 枚と前 $N-K$ 枚を順に出力すればよい。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, K; cin >> N >> K;
    vector<int> A(N); v_cin(A);

    vector<int> ans;
    rrep(i, N - K, N){
        ans.push_back(A[i]);
    }
    rep(i, N - K){
        ans.push_back(A[i]);
    }
    v_cout(ans);
}

B - Decrease 2 max elements

問題文の通りに、

  • $A$ を降順ソート
  • $A_0 \leftarrow A_0-1,~A_1 \leftarrow A_1-1$

を $A$ の正の要素の個数が $1$ 以下になるまで繰り返すという操作を行えばよい。 計算量は $O(N\log (N) \max(A))$ で十分に間に合う。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N; cin >> N;
    vector<int> A(N); v_cin(A);

    int ans = 0;
    while(true){
        sort(rall(A));
        ans ++;
        A[0] --; A[1] --;
        
        int cnt = 0;
        rep(i, N){
            if(A[i] > 0) cnt ++;
        }
        if(cnt <= 1) break;
    }

    cout << ans << '\n';
}

C - Triple Attack

愚直にシミュレーションすると $O(N\max (A))$ となって間に合わない。$T$ がどんな場合でも $3$ 回の行動で敵の体力を $5$ 減らすことができるので、任意の $1\leq i\leq N$ に対して $T \leftarrow T + \lfloor \frac{H_i}{5} \rfloor$ としたあとに、$H_i$ を $5$ で割った余りで場合分けする。
公式解説は、割った後は愚直にシミュレーションしていた。
計算量は $O(N)$ になる。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N; cin >> N;
    vector<int> H(N); v_cin(H);

    ll T = 1;
    rep(i, N){
        int q = H[i] / 5;
        int r = H[i] % 5;
        T += 3 * q;
        if(T % 3 == 0){
            if(r >= 1 and r <= 3) T ++;
            if(r == 4) T += 2;
        }else if(T % 3 == 1){
            if(r == 1) T ++;
            if(r == 2) T += 2;
            if(r >= 3 and r <= 4) T += 3;
        }else{
            if(r == 1) T ++;
            if(r >= 2 and r <= 4) T += 2;
        }
    }

    cout << T - 1 << "\n";
}

D - Minimum Steiner Tree

$V$ に含まれる点の $1$ つを根として考えれば、求める部分木は根を必ず含む。$dp_i$ を $i$ を根とする部分木の頂点のうち、求める部分木に含まれる頂点の数として定める。このとき、親のノードを $p$、子のノードの集合を $C$ とすると、$p \in V \text{ または } \sum_{c\in C}dp_c \geq 1$ のとき

\[dp_p = \sum_{c\in C}dp_c + 1\]

それ以外のとき $dp_p = 0$ となり解ける。わざわざDPを使う必要はないかもしれない。

int N, K;
vector<vector<int>> G;
vector<int> dp;
vector<bool> V;
vector<bool> visited;

void dfs(int pos){
    visited[pos] = true;
    int cnt = 0;

    rep(i, G[pos].size()){
        int nxt = G[pos][i];
        if(visited[nxt]) continue;
        dfs(nxt);
        cnt += dp[nxt];
    }

    if(V[pos] or cnt > 0) cnt ++;

    dp[pos] = cnt;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> K;
    G.resize(N);
    rep(i, N - 1){
        int a, b; cin >> a >> b; a --; b --;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    V.assign(N, false);
    rep(i, K){
        int v; cin >> v; v --;
        V[v] = true;
    }
    visited.assign(N, false);
    dp.assign(N, 0);

    rep(i, N){
        if(V[i]){
            dfs(i);
            cout << dp[i] << "\n";
            break;
        }
    }
}

F - Dividing Game

長さ $N$ の数列 $B$ を

\[B_i = A_i\text{ の素因数の個数 (重複あり)}\]

とすると、$B$ の Nim の問題に帰着できる。Nim の問題を解いたことがなかったので、鉄則本の該当ページを丸写しした。

vector<pair<long long, long long>> prime_factorize(long long N){
    vector<pair<long long, long long>> prime;
    for(long long i = 2; i * i <= N; i++){
        if(N % i != 0) continue;
        long long e = 0;
        while(N % i == 0){
            e++;
            N /= i;
        }
        prime.push_back({i, e});
    }
    if(N != 1) prime.push_back({N, 1});
    return prime;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; cin >> N;
    vector<int> A(N); v_cin(A);
    vector<int> ps(N, 0);
    rep(i, N){
        auto p = prime_factorize(A[i]);
        for(auto [x, y] : p){
            ps[i] += y;
        }
    }

    int sum = ps[0];
    rrep(i, 1, N){
        sum = sum ^ ps[i];
    }

    if(sum > 0) cout << "Anna\n";
    else cout << "Bruno\n";
}

コンテスト結果

コメント

来週までにNim と Grundy 数の話を勉強したい。