問題概要

$n (n \geq 2)$, $n$ は2のべき乗) 人のボクサーがトーナメントで戦い，優勝者を決めようとしている．

参加するボクサーは数列 $a_0, a_1, \cdots, a_{n-1}$ として与えられる (※問題文では 1-indexed ですが，解法説明の都合上 0-indexed で記載しています) ．ボクサーは強さの順にすでに並んでおり，$i \lt j$ のとき数列の $j$ 番目のボクサーは$i$ 番目のボクサーに勝利する．ただし $i$ 番目のボクサーは $a_i$ ドルの賄賂を渡せばわざと負けてくれる．

$a_i = -1$ は，あなたの友人である．あなたは友人を優勝させたい．

トーナメントはあなたが自由に組めるとして，友人を優勝させるのに必要な賄賂の最小額を求めよ．

解法概要

まず賄賂が存在しないとして Top $2^i (i \geq 0)$ まで残るには最弱でも何番目のボクサーでないといけないかを考えてみる．以下，$n = 2^{m}$ とする．

Top $2^{m-1}$ に残るためには，弱くとも 1番目のボクサーでないといけない．0番目 (= 最弱) のボクサーでない限り対戦カードによってはチャンスがあるからである．

Top $2^{m-2}$ に残るためには，弱くとも 3番目のボクサーでないといけない．どんなに弱いボクサーだけを集めたとしても，4人の中での最強にはならないといけないためである．

Top $2^{m-3}$ に残るためには，弱くとも 7番目のボクサーでないといけない．どんなに弱いボクサーだけを集めたとしても，8人の中での最強にはならないといけないためである．

同様に考えていくと，Top 2 には弱くとも $2^{m-1} - 1$ 番目のボクサーでなければならない．

そして，Top 1 (=優勝) には当然 $n-1$ 番目でなければならない．

このように考えていくと，友人が賄賂なしで何試合勝てるか，また，賄賂を渡さなければ勝てない試合は何試合かがわかる．

たとえば Example 2 は，

8
11 -1 13 19 24 7 17 5

となっており，友人は 1番目のボクサーである．そのため，Top 4 までは賄賂を渡さずとも勝ち残れる (0番目のボクサーと第一試合をすれば良い) が，優勝するには残りの2試合の対戦相手に賄賂を渡さなければならない．

次に渡す賄賂の額を最小化するように残りの2試合の対戦相手を決める．これは，

賄賂なしだと Top 1 になるボクサー (1人しかいないので選択の余地なし)
賄賂なしで，対戦カードによって Top 2 に入りうるボクサーの中でもっとも必要な賄賂の額が安いボクサー (ただし，1. で選んだボクサーは除く)

を選べば良い．ちなみにもう1試合賄賂を渡さなければならない場合があっても，

賄賂なしで，対戦カードによって Top 4 に入りうるボクサーの中でもっとも必要な賄賂の額が安いボクサー (ただし，1. か 2. で選んだボクサーは除く)

というように同様に最小値を考えていけばよい．

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

using ll =  long long;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n);
    for(int i=0;i<n;++i){
        cin >> a[i];
    }

    int n_need_win = 0; // 優勝までに勝たなければいけない試合数
    while(1 << n_need_win < n) ++n_need_win;
    int n_max_win = -1;  // 賄賂を渡さずに勝てる最大の試合数
    for(int i=0;i<n;++i) {
        if(i+1 == 1 << (n_max_win+1)) {
            ++n_max_win;
        }
        if(a[i] == -1) break;
    }

    if(n_max_win == n_need_win) {
        cout << 0 << endl;
        return 0;
    }

    int n_bribe = n_need_win - n_max_win;   // 賄賂を渡すべき人数
    int next_checkpoint = n-1;
    priority_queue<ll, vector<ll>, greater<ll>> que;    // 小さい順に取り出せるように後ろから見て a[i] を突っ込んどく用
    ll ans = 0LL;
    for(int i=n-1;i>=0&&n_bribe>0;--i) {
        que.push(a[i]);
        if(i == next_checkpoint) {
            ans += que.top();
            que.pop();
            next_checkpoint = ((next_checkpoint+1) >> 1) - 1;
            --n_bribe;
        }
    }

    cout << ans << endl;

}

所感

考察と実装の両方にバランスの良い重量感を感じる問題でした．ところでえでゅふぉのこの回の問題のストーリーたち，反政府組織だったり兵士を殺すトラップだったり友人を優勝させるための賄賂だったり色々と怖いですねぇ．

NoiminのNoise

Educational Codeforces Round 77 (Rated for Div. 2) E. Tournament

問題概要

解法概要

ソースコード

所感