【精進】ABC228 F - Stamp Game

いろいろ方法がある

問題概要

$H\times W$のマス目に正整数が書かれている。高橋くんが$H_1\times W_1$の領域を選び、それを見て青木くんが$H_2\times W_2$の領域を選ぶ。このときのスコアを高橋くんが選び、青木くんが選んでないマス目に書かれた整数の和とする。高橋くんがスコアを最大に、青木くんがスコアを最小にするような戦略を選ぶときスコアはいくらになるか？$H,W\le 10^3$

解法

青木くんは高橋くんが選んでないマス目を選んでもスコアに影響がないから$H_2\xleftarrow{\min}H_1,W_2\xleftarrow{\min}W_1$としてよい。またマス目には非負整数が書かれていることから、青木くんは高橋くんが選んだ領域の内部を選ぶとしてよい。 事前に2次元累積和をとることにより、長方形領域の和を$O(1)$時間で求められる。高橋くんがある領域を選んだ際に、その内部の$H_2\times W_2$の領域であって和が最大のものを青木くんは選ぶ。したがってこの操作を高速にできれば、全ての高橋くんが選びうる領域についてこれを計算することにより問題を解ける。(マス目の数字はstaticなため冗長だが)2次元セグメント木を使えば解ける。(1次元の)セグ木にセグ木を載せる形で実装し、クエリに対してセグ木を使い回す方法が思いつかなかったためその部分については別途書いた。

コード

#include "data_structure/segtree.hpp"
ll op1(ll a, ll b) {
    return max(a, b);
}
ll e1() {
    return 0;
}
using seg1 = segtree<ll, op1, e1>;
ll szw;
seg1 op(seg1 a, seg1 b) {
    vl v(a.n);
    rep(i, a.n) v[i] = max(a.get(i), b.get(i));
    return seg1(v);
}
seg1 e() {
    return seg1(szw);
}
void solve() {
    ll h, w;
    input(h, w);
    LL(h1, w1, h2, w2);
    chmin(h2, h1);
    chmin(w2, w1);
    szw = w - w2 + 1;
    ll szh = h - h2 + 1;
    Graph s(h + 1, vl(w + 1));
    rep1(i, h) rep1(j, w) {
        cin >> s[i][j];
    }
    rep(i, h) rep(j, w + 1) s[i + 1][j] += s[i][j];
    rep(i, h + 1) rep(j, w) s[i][j + 1] += s[i][j];
    auto aoki = [&](ll i, ll j) {
        return s[i + h2][j + w2] - s[i][j + w2] - s[i + h2][j] + s[i][j];
    };
    vector<seg1> _v;
    rep(i, szh) {
        vl v(szw);
        rep(j, szw) {
            v[j] = aoki(i, j);
        }
        _v.push_back(seg1(v));
    }
    segtree<seg1, op, e> seg(_v);
    ll ans = 0;
    auto takahashi = [&](ll i, ll j) {
        return s[i + h1][j + w1] - s[i][j + w1] - s[i + h1][j] + s[i][j];
    };
    auto query = [&](ll l, ll r, ll L, ll R) {
        ll res = 0;
        l += szh, r += szh;
        while(l < r) {
            if(l & 1) {
                chmax(res, seg.v[l].prod(L, R));
            }
            if(r & 1) {
                chmax(res, seg.v[(r - 1)].prod(L, R));
            }
            l = (l + 1) >> 1;
            r >>= 1;
        }
        return res;
    };
    rep(i, h - h1 + 1) {
        rep(j, w - w1 + 1) {
            ll tmp = takahashi(i, j);
            tmp -= query(i, i + h1 - h2 + 1, j, j + w1 - w2 + 1);
            chmax(ans, tmp);
        }
    }
    print(ans);
}
int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
}

2次元セグ木は初めて使ったので、もう少し勉強する必要がありそう。

別解

高橋くんが選んだ領域に対して、青木くんが選ぶ可能性のある領域は$(H_1-H_2+1)\times(W_1-W_2+1)$個ある。これが固定なのでスライド最大値を用いて計算できる。

コード

#include "template.hpp"
void solve() {
    LL(h, w, h1, w1, h2, w2);
    chmin(h2, h1);
    chmin(w2, w1);
    Graph s(h + 1, vl(w + 1));
    rep1(i, h) rep1(j, w) {
        cin >> s[i][j];
    }
    rep(i, h) rep(j, w + 1) s[i + 1][j] += s[i][j];
    rep(i, h + 1) rep(j, w) s[i][j + 1] += s[i][j];
    auto cul_aoki = [&](ll i, ll j) {
        return s[i + h2][j + w2] - s[i][j + w2] - s[i + h2][j] + s[i][j];
    };
    Graph aoki(h - h2 + 1, vl(w - w2 + 1));
    rep(i, h - h2 + 1) rep(j, w - w2 + 1) {
        aoki[i][j] = cul_aoki(i, j);
    }
    auto slide_max = [](vl &v, ll k) {
        ll n = ssize(v);
        vl res(n - k + 1);
        deque<ll> d; // idx列 v[d[i]]は狭義単調減少
        rep(i, n) {
            if(d.size() and d[0] + k == i)
                d.pop_front();
            while(d.size() and v[d.back()] <= v[i])
                d.pop_back();
            d.push_back(i);
            if(i >= k - 1)
                res[i - (k - 1)] = v[d[0]];
        }
        return res;
    };
    Graph aoki2(h - h2 + 1);
    // aoki2[i][j] = max(aoki[i][j],..,aoki[i][j+(w1-w2)])
    rep(i, h - h2 + 1) {
        aoki2[i] = slide_max(aoki[i], w1 - w2 + 1);
    }
    Graph aoki3(h - h1 + 1, vl(w - w1 + 1));
    // aoki3[i][j] = max(aoki[i][j],...,aoki[i+(h1-h2)][j])
    //             = max[k<=h1-h2,l<=w1-w2](aoki[i+k][j+l])
    rep(j, w - w1 + 1) {
        vl v(h - h2 + 1);
        rep(i, h - h2 + 1) v[i] = aoki2[i][j];
        v = slide_max(v, h1 - h2 + 1);
        rep(i, h - h1 + 1) aoki3[i][j] = v[i];
    }
    ll ans = 0;
    auto takahashi = [&](ll i, ll j) {
        return s[i + h1][j + w1] - s[i][j + w1] - s[i + h1][j] + s[i][j];
    };
    rep(i, h - h1 + 1) rep(j, w - w1 + 1) {
        chmax(ans, takahashi(i, j) - aoki3[i][j]);
    }
    print(ans);
}
int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
}

スライド最大値についてはここを参考に書いた。ところでスライド最大値(最小値)については公式解説にも説明があるが、無駄に$\log$が掛かっているように見える。気のせいだろうか？