D - Pond
問題とかは↑のリンク見て！！
回答、考察kobashun5848.icon
中央値が最も小さくなる区画を探す
しらみ潰しでやると$ O(N-K)^2 * (k^2個の要素のソートの計算量)がかかってしまう？
ある区間の中央値がX以上である ⇔ ある区間に含まれるX以上の数の個数がK2/2+1以上であると置き換えれるかが鍵
「中央値がX以下となるような区画はあるのか」⇔「Xより大きい要素がK2/2+1個未満の区画はあるのか」と置き換えれる
キーポイント・・・中央値の捉え方、二分探索、二次元累積和
Atocoder 公式の解説は参考になるよ
code:swift
return readLine()!.split(separator: " ").map { Int($0)! }
}
func range(_ s: Int, _ e: Int) -> Range<Int> { s..<e }
func pond(){
//初めのN,Kを読み込む
let input = readInts()
//N×Nの二次元配列を読み込む
var matrix: Int = (1...n).map{ _ in readInts()}
// sはある区間に含まれるmid以上の数値の数を表している。ex)Si+1j+1はmatrix00~matrixijまでに含まれるmid以上の数 var s = Int(repeating: Int(repeating: 0, count: n + 1), count: n + 1) // 「中央値がok以下となる区画は存在する」 , 「中央値がng以下のものは存在しない」 という関係となるok,ngを格納する
var ng = -1, ok = 1000000000
// ng+1 < ok の関係が崩れた時、求めたい最終的なOKが決まるのでそれまでループを回す
while ng + 1 < ok {
// 中央値の初期値を設定
let mid = (ng + ok) / 2
// sを計算
for i in range(0, n) {
for j in range(0, n) {
}
}
var ext = false
let limit = k * k / 2 + 1
for i in range(0, n - k + 1) {
for j in range(0, n - k + 1) {
// sの二次元累積和を計算している
//「全ての区画のうち、１つでも合計が limit 未満である」ー＞「中央値がmid以下となる区画がある」ー＞「est
ext = true
}
}
}
// 「est---->false」ーーー＞「中央値がmid以下となる区画がない」ーーー＞ngの更新 if ext {ok = mid} else {ng = mid}
}
print(ok)
}
pond()