Educational Codeforces Round 43 E. Well played!

公式解説を理解するのに時間がかかったので日本語の記事を書いておきます.
(現時点で日本語の記事は見つけられませんでした)

解説

便宜上,問題文にある二つの spell を「呪文 A」「呪文 B」と呼ぶことにします.

呪文 A の使い方

公式解説にある背理法の証明は個人的にはやや理解しづらかったですが, 要するに「呪文 A は一体に集中させても損しない」ということです. ここでは「どの一体を選ぶのが最適か」という話まではしていないです. あくまで,「呪文 A を使うなら一体に集中させても損しないので,その方が議論が簡単になる」ということだけ言っています.

よって, i 番目の creature に呪文 A を使うと決めたときには  hp^{'}_{i} = hp_{i} \times 2^{a} としてよいです.

呪文 B の使い方

呪文 B を  (n + 1) 回以上使う必要はないので  b = \mathrm{min}(b, n) としておきます.

どの creature に呪文 B を使うべきかを考える必要がありますが, これは「 dmg_{i} の代わりに  hp_{i} を使ったら(=呪文 B を使ったら)どのくらい得をするか」に着目して,  hp_{i} - dmg_{i} の降順ソートをすることでその利得の大きい順に creature を並べることができます(相対評価). 最大  b 体にしか呪文 B は使えないので,上位  b 体にだけ呪文 B を使うことを検討すれば十分です. ただし,この時点では呪文 A を考えていないことに注意してください. また,利得がマイナスの場合は呪文 B を使わない方が得なので呪文 B は使いません (使わずに余った分を後半の creature に回す必要もありません.なぜなら,利得の大きい順にソートしているので,利得マイナスが生じたら,その後もずっと利得マイナスが続くからです).

答えの求め方

方法は色々あると思いますが,ここでは公式解説ベースの説明をします.

まずは呪文 A を使わないで答えを仮計算しておきます. 利得マイナスのときは呪文 B を使うべきではありませんが, 実装上は  \mathrm{max}(hp_{i}, dmg_{i}) で評価してしまうと簡単です.

次に呪文 A の使用を考慮して答えを最適化します. 「呪文 A はどの一体に使うべきか?」を探索なしに特定するのは恐らく不可能であるため 「 i 番目の creature に呪文 A を使った場合は答えがいくつになるか?」を愚直に全探索します. このとき,先ほど行った降順ソートの順で調べていき,上位  b 体かそれ以降かで場合分けします.

  •  1 \leq i \leq b 番目
    •  i 番目の寄与  \mathrm{max}(hp_{i}, dmg_{i}) を一時的に引き算する
    • 代わりに  hp^{'}_{i} = hp_{i} \times 2^{a} を足し算して評価する
  •  b + 1 \leq i \leq n 番目
    •  i 番目には呪文 B が使えないので, b 番目に使っている呪文 B を取りやめて  i 番目に使う
      • 「呪文 B をどこから拝借するか?」は利得が最も小さい creature を選ぶのが最適
    •  b, i 番目に対して一時的な引き算と足し算をした上で評価する(前半の場合と同じ要領)

これで最適解が求まります.

所感

最初は  dp[n][a] の DP を考察していたんですが,「呪文 B を誰に使うか?」が残って上手くいきませんでした. こういう場合には greedy で考察できるようにしていきたいです.

解答例

https://codeforces.com/contest/976/submission/114846390

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
 
    ll N, A, B; cin >> N >> A >> B;
    VLL h(N),d(N); REP(i,N) cin >> h[i] >> d[i];
 
    ll x = (1LL<<A);
    chmin(B, N);
 
    vector<tuple<ll,ll,ll>> X(N);
    REP(i,N) X[i] = tuple(h[i] - d[i], h[i], d[i]);
    RSORT(X);
 
    // b のみで仮計算
    ll tmp = 0;
    REP(i,N) {
        auto [_, hh, dd] = X[i];
        if (i < B) {
            tmp += max(hh, dd);
        } else {
            tmp += dd;
        }
    }
 
    // b が 0 なら
    if (B == 0) {
        COUT(tmp); return 0;
    }
 
    // a を考慮して最適化
    ll ans = tmp;
    REP(i,N) {
        auto [_, hh, dd] = X[i];
        if (i < B) {
            tmp = (tmp - max(hh, dd) + hh*x);
            chmax(ans, tmp);
            tmp = (tmp + max(hh, dd) - hh*x);
        } else {
            // b 番目に使っていた b を取りやめて i 番目に使用 & a を使用
            auto [_, hh2, dd2] = X[B-1];
            tmp = (tmp - max(hh2, dd2) + dd2);
            tmp = (tmp - dd + hh*x);
            chmax(ans, tmp);
            tmp = (tmp + dd - hh*x);
            tmp = (tmp + max(hh2, dd2) - dd2);
        }
    }
    COUT(ans);
 
    return 0;
}