2018-08-30

AtCoder AGC 026 F - Manju Game (銀色, 2000 点)

パリティ DP 二分探索ゲーム条件の言い換え DP値を利用して状態復元 AtCoder AGC-F AtCoder2000～点区間区間分割型シーケンシャルDP DP高速化最大値の最小化数列操作操作木を考える銀色diff DP高速化:直前との比較のみでよい

ふと考えてみた。区間 DP っぽく $O(N^{3})$ にはなるな...なんて思っていたけどそこから落とせなかった...いやこれ何を食べたらこんな二分探索思いつけるようになるの！？！？！？！？？？

なにかこういう場面で二分探索すると上手く行くよ、というパターン的なものがあるのだろうか...

問題へのリンク

問題概要

$N$ 要素の数列 $a_1, a_2, \dots, a_N$ が与えられる。先手と後手が交互に以下のようなゲームを行う ( $N$ ターン):

相手が最後にとった数に隣接する数のうち、まだとられていない数をとる
上記の条件を満たす数が存在しないとき、および最初の先手のターンでは好きな数をとる

両者とも最終的にとった数の合計を最大化したい。互いに最適戦略をとったときの 2 人の得点を求めよ。

制約

$1 \le N \le 3×10^{5}$

解法

どこかのマスをとったら、左右どちらかを削り続けて、また残ったところのどこかマスをとったら、左右どちらかに削り続けて、、、を繰り返すゲームになる。

どこかのマスをとったとき、左右に残っているマス目の個数の偶奇性が決定的に重要なので、マス目を白黒に塗ることにする。0 番目, 2 番目, ... のマスを黒で、1 番目, 3 番目, ... のマスを白で塗る。

N が偶数のとき

左端を最初にとれば先手は「黒を全部とる」が実現できて、右端を最初におちれば先手は「白を全部とる」が実現できる。

よって、先手は max(黒, 白) 以上を得点できることが保証される。それ以上の得点を取ろうとした場合には、後手がそれを阻止できることが以下のようにわかる:

先手が最初に任意の黒のマスをとった場合: 後手はその左の白をとる (そうすれば左に左に削っていったときに最後に左端の黒をとるのは先手なので、後手はその後の展開の主導権を握れる)
先手が最初に任意の白のマスをとった場合: 同様に後手はその右の黒をとればいい

以上より、先手は max(黒, 白)、後手は min(黒, 白) を獲得するのが最大となる

N が奇数のとき

まず N が偶数のときと同様の考察によって

先手は黒全部をとることはできる

は言える。また先手後手に限らず

奇数長の盤面で主導権を握ったときに、端っこ以外の黒をとる意味はない

ということも言える。なぜなら、そのとき後手に左の白をとられた場合、左端の黒を先手がとることになって後手に主導権を握られてしまう。

よって先手としてやることは

左端または右端の黒をとる (つまり残盤面の黒をすべてとる)
どこかの白をとる

のみとなる。どこかの白をとったとき、後手は左右どちらの黒を選んだとしても、最終的には後手が端をとることとなり、先手が残った盤面の主導権を握ることができる。主導権を握ってからは上のことを繰り返すことになる。

よって区間 DP 的なアプローチによって再帰的に解くことができそう。先手が白を選んだときに、後手が左右どちらをとるべきかは再帰的に求めることができる。これで $O(N^{3})$ にはなった。僕はここから計算量を落とせなかった。

ゲームの構造をわかりやすく特徴付ける

こういう場合、「先手が取りうるもの」がどうなるのかを特徴付けることを考えるのがよい気がする。

先手は、

残盤面において
- どこかの白をとる
- 諦めて左端または右端の黒をとる (そしてゲームは終了する)

の選択を繰り返すことになる。したがって、残盤面で先手がとっていく白の index が W1, W2, ..., Wk とすると、k+1 個のパートにわかれて、先手が取る分は

W1, W2, ..., Wk と、k+1 個のパートにうちの k 個の「白全部」と、残り 1 個の「黒全部」

という感じになる。後手は、先手の W2, W3, ... の選び方や、最後の黒区間をコントロールすることができる。まとめると

先手はあらかじめ、W1, ... をノードにもつ二分木を持っておく
後手は二分木のどちらに進むかを選択する

という感じになる。つまり、先手は k+1 個の区間をあらかじめ形作っておき、後手はその区間のうち先手が一番損をするものを選んで先手に「全部黒」を押し付けることができる。

したがって先手にとっての最適化問題とは、

白の総和 + (k +1 個の区間についての「黒の総和 - 白の総和」の最小値)

を最大化したいという問題になる。

二分探索へ

最初の editorial を見て「二分探索」という単語を見た時は驚愕したけど、ここまでゲームの構造の特徴付けができれば確かに自然かもしれない。最小値を最大化したい問題に落とし込まれているから、二分探索したくなる。

パラメータ X について、先手が適切に k 個の白を選んで、k + 1 個の区間に分割して、すべての区間について「黒の総和 - 白の総和」を X 以上にできるか

を判定する問題を解く。りんごさんはここまで来れば簡単と言っていたが、これでもまだそこまで簡単には思えない... $O(N^{2})$ な DP はすぐなのだが...少し考えれば以下のような DP で OK

dp[ i ] := 区間 [0, i) を最後の区間以外は「黒 - 白」が X 以上を保証した上で上手く分割したときに、最後の区間についての「黒 - 白」の取りうる最大値

よって二分探索の毎回のステップの判定は $O(N)$ でできる。全部で $O(N\sum{a_{i}})$ でできる。

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

int N;
vector<long long> a;

int main() {
    cin >> N;
    long long black = 0, white = 0;
    a.resize(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
        if (i % 2 == 0) black += a[i];
        else white += a[i];
    }
    if (N % 2 == 0) cout << max(black, white) << " " << min(black, white) << endl;
    else {
        long long low = 0, high = 1<<30;
        while (high - low > 1) {
            long long mid = (low + high) / 2;
            vector<long long> dp; dp.assign(N + 1, -(1LL << 60));
            dp[1] = a[0];
            for (int i = 3; i <= N; i += 2) {
                // 直前をカットする場合
                if (dp[i - 2] >= mid) dp[i] = max(dp[i], a[i - 1]);
                
                // 直前をカットしない場合
                dp[i] = max(dp[i], dp[i - 2] - a[i - 2] + a[i - 1]);
            }
            if (dp[N] >= mid) low = mid;
            else high = mid;
        }
        cout << white + low << " " << black - low << endl;
    }
}

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

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