Pond [AtCoder Beginner Contest 203（Sponsored by Panasonic） D]

https://atcoder.jp/contests/abc203/tasks/abc203_d

前提知識

• 二分探索
• 二次元累積和

解説

https://atcoder.jp/contests/abc203/submissions/23075536

二分探索しよう。
始めてみる・慣れていない場合はピンとこないと思うが、最大値の最小値というのが二分探索では定番であり、
中央値の最小値で使われる場合も何回か見たことがあるのでスムーズに思いついた。
経験以外で思いつくトリガーあるのかな？ちょっと分からない。

二分探索

check(lim) := 全ての区間の中央値がlim以上であるかどうか

これを[0,∞)の範囲で判定問題を考えると、True True .... True False False ...のような分布となり、この境目のTrueが答えになる。

判定関数

とある区間の中央値がlim以上であることをいかに判定するかであるが、

とある区間の中央値がlim以上である ⇔ とある区間に含まれるlim以上の数の個数がK²/2+1以上である

と言い換えることができる。
この言い換え後の条件を見るとすべての数は

• lim以上
• lim未満

のどちらかに分別することができ、「分別後は具体的な数値は使用されない」ことになる。
よって行列の値をすべて0/1にすることができて、その1の個数を高速に取得できれば判定が高速にできる。

これには二次元累積和を使おう。区間の和を求めるのに累積和を使うと思うが、それを二次元に拡張したものがある。
詳しい実装は「二次元累積和」でググってもらえば出てくると思う。
自分はライブラリ化してしまっている。

int N, K, A[808][808];
//---------------------------------------------------------------------------------------------------
int check(int lim) {
    Ruisekiwa2D r2d(N, N);
    rep(y, 0, N) rep(x, 0, N) if (lim <= A[y][x]) r2d.add(x, y, 1);
    r2d.build();

    rep(y, 0, N - K + 1) rep(x, 0, N - K + 1) {
        int tot = r2d.get(x, x + K - 1, y, y + K - 1);
        if (tot < K * K / 2 + 1) return false;
    }
    return true;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) rep(j, 0, N) cin >> A[i][j];

    int ok = 0, ng = inf;
    while (ok + 1 != ng) {
        int md = (ok + ng) / 2;
        if (check(md)) ok = md;
        else ng = md;
    }
    cout << ok << endl;
}