ABC203 D - Pond (400)
愚直に解こうとすると
$ K^2
マス
$ (N-K)^2
個から平均値を取る必要があり、
$ \mathcal{O}(n^2 k^2)
になる
二分探索で答えを求める
閾値を決めてそれ以上かどうかでそれぞれのマスを0/1で表すことができる
0/1で表すとある区画に閾値以上がいくつあるかが定数時間で求まるようになる
全体で
$ \mathcal{O}(n^2 \log \max A)
で求まる
問題:
https://atcoder.jp/contests/abc203/tasks/abc203_d
提出:
https://atcoder.jp/contests/abc203/submissions/23058751
#ABC203
#400pt
#D
#ABC
#AtCoder