データを上手に持って、差分更新する系の問題

問題へのリンク

問題概要

$H \times W$ のグリッドがあって、各マスは文字 '#' か '.' のいずれかが書かれている。先手は '#' の個数が得点となり、後手は '.' の個数が得点となる。双方得点を最大化したい。

先手は行を 1 つ選んで、その行の '#' と '.' を flip する
後手はその後、列を 1 つ選んで、その列の '#' と '.' を flip する

双方最善を尽くしたときの、先手と後手が得られる得点を求めよ。

制約

$H \times W \le 5 \times 10^{5}$

考えたこと

このように「先手が得点を伸ばそうとすると後手の得点が下がり、後手が得点を伸ばそうとすると先手の得点が下がる」というような構造のゲームは、一見手の付け所が難しいですね。なお、このようなゲームをゼロサムゲームと言ったりもします。

このようなゼロサムゲームの問題でよくやるアプローチとして、先手の手を固定したときの、後手の最適戦略を求めてみましょう。まずは、簡単のため、先手が何もしなかった場合を考えます。つまり、

与えられた盤面において
適切に列を選んで flip して
'#' の個数を最小にする (= '.' の個数を最大にする)

方法を考えればよいです。これはそれほど難しくなくて、後手の最適戦略は

'#' の個数が最も多い列を選んで flip する

となります。

先手の手を固定したときの、後手の手を求める

それでは、具体的に先手が行 $i$ を flip したときの、後手の最善手を求めましょう。

このとき、先手の flip 操作後の盤面について、各列の '#' の個数を数えるような作業を行なっていては計算時間が厳しいです。

先手の手： $O(H)$ 通り
flip 操作後の盤面で、各列の '#' の個数を愚直に求める： $O(HW)$ の計算量

となりますので、全体の計算量は $O(H^{2}W)$ となります。なお、これで小課題 6 (74 点) まで取れます。

高速化

最後に高速化しましょう。先手が行 $i$ を flip するとき

「各列の '#' の個数はあまり変化しない」

ということに着目します。そこで、あらかじめ最初の盤面について

num[j] ← 各列 $j$ に含まれる '#' の個数

を求めておきます。そして、先手が行 $i$ を flip するとき、各列 $j = 0, 1, \dots, W-1$ について

もし、マス $(i, j)$ が '#' ならば、--num[j] とする (列 $j$ の '#' が減るため)
もし、マス $(i, j)$ が '.' ならば、++num[j] とする (列 $j$ の '#' が増えるため)

というように更新すればよいでしょう。

この工夫を盛り込むと、全体の計算量は $O(HW)$ となります。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 入力
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (int i = 0; i < H; ++i) cin >> S[i];
    
    // 行に何もしなかった場合の、各列の '#' の個数を求める
    vector<int> num(W, 0);
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (S[i][j] == '#') {
                ++num[j];
            }
        }
    }
    
    // 各行について考える
    int res = 0;
    for (int i = 0; i < H; ++i) {
        // i 行目を flip したときの各列の '#' の個数
        vector<int> num2 = num;
        int sum = 0;  // flip 後の '#' の総数
        for (int j = 0; j < W; ++j) {
            if (S[i][j] == '#') --num2[j];  // 減る
            else ++num2[j];  // 増える
            sum += num2[j];
        }
        
        // 凛は num2 が最も多い列を選ぶ
        int max_sharp = 0;
        for (int j = 0; j < W; ++j) {
            max_sharp = max(max_sharp, num2[j]);
        }
        
        // その列をひっくり返すと、その列の '#' の個数が、max_sharp -> H - max_sharp になる
        sum -= max_sharp;
        sum += H - max_sharp;
        res = max(res, sum);
    }
    cout << res << " " << H * W - res << endl;
}

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

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

JOIG 2023 D - コイン集め 2 (難易度 6)

問題概要

制約

考えたこと

先手の手を固定したときの、後手の手を求める

高速化

コード