この問題は 問目と難易度が大きく違い、戸惑った方も多いと思います。
以下の判定問題を考えてみましょう。
- 収穫した小麦の成長度の最小値として 以上を達成できるか？
この判定問題を解くうえでは、小麦の成長度は 以上であるかどうかしか関係ありません。
また、成長度が 以上の小麦が 本以上ある場合は、少なくとも問題の答えとして 以上を達成できます。
ここで、 以上の小麦の成長度は 、それ以外は とみなすと、二次元累積和を用いることによって該当する小麦の本数を高速に計算できます。
判定問題には単調性があるため、二分探索を用いるとこの問題を全体で で解くことができます。
実装例(C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, m, k;
cin >> n >> m >> k;
vector<vector<long long>> a(n, vector<long long>(n));
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> a[i][j];
}
}
long long ok = -1, ng = 1.1e9;
while(abs(ok - ng) > 1){
long long mid = (ok + ng) / 2;
vector<vector<long long>> t(n, vector<long long>(n));
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(a[i][j] >= mid) t[i][j] = 1;
else t[i][j] = 0;
}
}
vector<vector<long long>> sum(n + 1, vector<long long>(n + 1));
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
sum[i+1][j+1] += sum[i+1][j] + sum[i][j+1] - sum[i][j] + t[i][j];
}
}
long long mx = 0;
for(int i = 0; i < n - m + 1; i++){
for(int j = 0; j < n - m + 1; j++){
mx = max(mx, sum[i + m][j + m] - sum[i + m][j] - sum[i][j + m] + sum[i][j]);
}
}
if(k <= mx){
ok = mid;
}else{
ng = mid;
}
}
cout << ok << endl;
}