ABC203 D 解答
D - Pond（1622）
問題
問題文
AtCoder 公園の敷地は東西南北に広がる N×N のマス目からなっており、北から i 番目かつ西から j 番目のマスの高さは Ai, j で与えられます。
公園の管理者である高橋君はここに K×K の区画の池を作る事にしました。
池を作るにあたって、高橋君は AtCoder 公園の敷地内に完全に含まれる K×K の区画であってその区画に含まれるマスの高さの中央値が最も低いようなものを選ぼうと考えました。そのような区画のマスの高さの中央値を求めてください。
ここで、K×K の区画に含まれるマスの高さの中央値とはその区画に含まれる
K^2 個のマスのうち ⌊K^2/2⌋+1 番目に高いマスの高さを指します。また、⌊x⌋は
x以下の最大の整数を表します。
制約
1 ≤ K ≤N ≤ 800
0 ≤ Ai, j ≤ 10^9
入力は全て整数である。
考察
本記事では
2分探索＋累積和を用いた差分
を用いた解法を説明します。一つずつ説明していきます。
１）2分探索
本課題で求めるのは
中央値の最小値
ですね。「最大値の最小値」や「最小値の最大値」を求める場合は2分探索が使えることが多いです。これを中央値に適用することで、本問題も解くことが可能です。
2分探索で大切のなのは、決め打った値に対して「実現可能」か「実現不可能」かを判定することです。まずは、具体的な例を用いて考えましょう。
例）2 4 4 6 9 9 10 14 18
とします。本問題では中央値が
K×K の区画に含まれるマスの高さの中央値とはその区画に含まれる
K^2 個のマスのうち ⌊K^2/2⌋+1 番目に高いマスの高さを指します。
と定められています。K=3と考えると、 9 / 2 + 1 = 5 番目に大きな値（右から5番目）が中央値になるそうです。となると、9 ですね。右から 5 番目ということは左からも 5 番目です。要素数が奇数なのでこうなります。
では、次に同様な数列を3つ書きます。このうちでどれが中央値が9以下になるかわかりますか。
１：1 2 3 4 5 6 7 8 9
２： 8 9 10 11 12 13 14 15 16
３： 5 5 5 5 5 7 10 13 15
どうでしょうか。各列の中央値は「5」「12」「5」ですので、答えは「１と３」です。左から5番目の値が中央値となるので、5番目の数字が9以下であれば条件を満たせます。言い換えますと、9以下の数が5個以上あればこの条件を満たすことができます。
もう少し条件を厳しくしましょう。中央値を4以下にすることは可能でしょうか。
この場合も4以下の数が5個以上あれば条件達成、なのですが、どれも満たせそうにありません。１）が最も多いですが、それでも４個です。この場合ですと、中央値に選ばれるのはその次の値になります。実際その次の５が中央値になってます。
少しだけ見えてきましたね。今度は偶数個の列を考えます。
例）1 5 8 9
この時の中央値は5ですね。右から3番目、左から2番目です。奇数個の例と比較してみますと
奇数 9：左から5番目
偶数 4：左から2番目
ですね。よくよく見ますと、各数字の切り上げ演算の値になっています。
ここまで情報がそろいましたので、2分探索のやり方をまとめてみます。
１）初期値OK = 1e9+1,NG=-1を設定する。
２）mid = (OK+NG)/2を計算する。
３）N*Nある池の全部の場所に対してその値がmid以下であるか調べる。
４）K*Kの領域でmid以下の値が「K*K/2の切り上げ」個以上あるか調べる。
５）条件を満たせばOK=mid、満たさなければNG=midとして２）に戻る。
これを、OK-NG=1となるまで続けます。この時のOKの値が答えになります。
これで2分探索はおしまいです。ただし、この過程の中でネックなのは
４）K*Kの領域でmid以下の値が「K*K/2の切り上げ」個以上あるか調べる。
こいつです。これを愚直に実装すると
K * K * (N-K) * (N-K)
だけかかります。これはさすがに厳しいです。ですので、累積和を使って高速化します。次の状態を考えてみましょう。
左にて1となっているのが、ある数 X よりも小さい数です。また、累積和は各行ごとに取っており、先頭に0を付けています。
例えば、(1,0)から(1,2)までに含まれる1の数は3-1=2と求めることが可能です。このように横方向になら一発で1の数を求められます。
これを、K行分行うとある区間の1の数が求まります。それを、K*Kをずらしながら全部の領域に行えば、判定ができます。
が、これでも間に合いません。もう少しだけ工夫しましょう。今度は縦方向にずらした時の差分を取ってみましょう。領域を一つずらしますと、一番上の行が領域から外れて、一つ下の行が新たに加わります。領域に含まれる1の数はその差分だけ変化します。
これを行うと、K行分行うのは各列に対して1回だけ計算すれば良くなります。縦方向にずらす際には上と下の2回の計算で済みますね。これは速くなりそうです。
緑の値を引いて、新たな赤の値を足すと1の数が求まりますね。
このように1の数を求めまして、ある中央値 X 以下かどうかを判定してあげましょう。
考察は以上です。
実装
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main()
{
int n, k;
cin >> n >> k;
vector<vector<int>> A(n, vector<int> (n));
rep(i, n)rep(j, n)cin >> A[i][j];
int ac = 1e9 + 5;
int wa = -1;
while (ac - wa > 1)
{
int wj = (ac + wa) / 2;
vector<vector<int>> S(n+1, vector<int>(n+1));
int judge = 0;
rep(i, n)rep(j, n)
{
if (A[i][j] <= wj) S[i][j+1] = S[i][j] + 1;
else S[i][j+1] = S[i][j];
}
for (int j = 0; j < n - k + 1; ++j)
{
int now = 0;
rep(p, k)
{
now += S[p][j + k] - S[p][j];
}
judge = max(judge, now);
for (int i = 0; i < n - k; ++i)
{
now -= S[i][j + k] - S[i][j];
now += S[i+k][j + k] - S[i + k][j];
judge = max(judge, now);
}
}
if (judge >= (k*k + 1) / 2) ac = wj;
else wa = wj;
}
cout << ac << endl;
return 0;
}あとがき
今回は2分探索＋累積和の差分で計算しました。本問題の想定解は2次元累積和みたいですね。非常に重要な内容ですので、もしこの記事を読んでいただいた方も、そちらの方も勉強しておいてください。他の方々の優秀な記事が見つかると思います。
ただ、私は差分で解く方法を紹介しました。あまりスマートではないですが、
コンテスト中はとにかく手を動かすこと
を伝えたかったからです。私は2次元の累積和を知りませんでしたが、どうにか解けないかな、と色々考えていたらこの解法にたどり着きました。コンテスト中はどんな解法でもACした人の勝ちです。もちろん速いほうが良いのですが、そもそも解けなければお話になりません。
諦めそうになっても、どうにか正解にたどり着けないか、ともう一度考えてみると、もしかしたらACが降ってくるかもしれません。
部活の熱血指導みたいな文章になりましたが、ギリギリまで悩んで、なんとかACするととっても気持ちいいよ、ということだけわかってもらえたらな、と思います。
この記事が気に入ったらサポートをしてみませんか？