ある量を、一方は最大化したくて、他方は最小化したいというゲーム。これは

ゲーム DP で解けるなら楽
ゲーム DP で解けるほど探索領域が小さくないなら、ある値が存在して、以下を示す
- 先手は少なくとも $x$ 以上を達成できること
- 後手は少なくとも $x$ 以下を達成できること

という風にすることが多そうなきがする。こういう $x$ を見出すのが難しいけど、こういうのは

後手の動きを固定したときに先手はどう動くのが最適か
先手の動きを固定したときに後手はどう動くのが最適か

という方向性で考えると見えてくることが多い気がする。そういう考察が特に重要となる類題として、以下など

drken1215.hatenablog.com

問題へのリンク

問題概要

長さ $N$ で総和が等しい 2 つの数列 $A, B$ が与えられる。

任意のターンにおいて、 $A = B$ となった時点で試合終了である (初期盤面で終了なこともある)
先手は $A$ の要素を一つ選んでデクリメントする
後手は $B$ の要素を一つ選んでデクリメントする

というのを $A = B$ となるまで繰り返す。試合終了時までに先手がデクリメントした量 (= 後手がデクリメントした量) がこのゲームのスコアとなる。

先手はスコアを最大化したい。後手はスコアを最小化したい。双方最善を尽くしたときのスコアを求めよ。

制約

$1 \le N \le 2 \times 10^{5}$

考えたこと

こういう頭がごちゃごちゃするときは、ひとまず一方の動きを固定したときに他方がどう動くのが最善かを考えよう。後手を固定してみる。

先手は $A_{i} \gt 0$ , $A_{i} \le B_{i}$ となる $A_{i}$ があるうちはそれをすべて 0 にしてしまうことができる。そして後手も最終的には全部 0 にしなきゃダメという状況に追い込める
その後は $A_{i} \gt B_{i}$ となる $i$ について $A_{i}$ を下げることを余儀なくされるのだが、もし他に $A_{j} \gt B_{j}$ となる $j$ が残っていたら、 $A_{i} = B_{i}$ となった瞬間に、まだ先手は $A_{k} = 0$ , $B_{k} \gt 0$ な $B_{k}$ を小さくするタスクが残っている状態になっている。
- よって先手がそっちにかまけている間に $A_{i}$ をさらに下げてしまえば OK

ということから、 $A_{i} \gt B_{i}$ となる $i$ が最後の 1 個になるまでは、結局全部の $A$ を $0$ まで下げることができるのだ！！！！！！！

以上から言えることは、数列の総和を $S$ 、 $A_{i} \gt B_{i}$ を満たす範囲内での $B_{i}$ の最小値を $m$ として

先手は少なくとも $S - m$ 以上のスコアを達成できる

ということ。直感的にはこれがもう答えになりそうな気がする。

後手目線

次に後手目線で考えてみる。後手としてはなんとしても $S - m$ で抑えたい。

で、これはもう明らかで、 $A_{i} \gt B_{i} = m$ を満たす $i$ に対しては $B_{i}$ をそのままにしておけばいいのだ。それさえ守れば割とテキトーでよくて、どのみち先手がそれ以外の $i$ に対してはすべて 0 にしてしまうのを防ぐことができない。そしてそれらに対して後手も 0 まで追いついたときにはちょうどピッタリ $A_{i} = B_{i} = m$ の状態になってゲームは終了する。

よって後手としても $S - m$ を達成することができる。

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<long long> A, B;

long long solve() {
    if (A == B) return 0;
    long long sum = 0, mi = 1LL<<60;
    for (int i = 0; i < N; ++i) {
        sum += A[i];
        if (A[i] > B[i]) mi = min(mi, B[i]);
    }
    return sum - mi;
}

int main() {
    cin >> N;
    A.resize(N), B.resize(N);
    for (int i = 0; i < N; ++i) cin >> A[i] >> B[i];
    cout << solve() << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ARC 094 E - Tozan and Gezan (青色, 700 点)

問題概要

制約

考えたこと

後手目線