ABC075 DAxis-Parallel Rectangle

所見

50⁵解は自明だが、10⁸はよほど軽くないと通らない、と思っていたので嘘高速化を始めてハマった。この問題から学ぶことは多くないが、50⁵でも十分通るという事実は大いに学びである。

問題概要

座標平面上にN個の点がある。内部にK個以上の点を含む長方形のうち、面積が最小となる長方形の面積を求めよ。

取った方針

各辺が長方形の辺上にくるとき面積が最小になるのはすぐにわかる。それにより上下左右の座標を全探索し、さらにすべての点について走査して長方形の内部に含まれるかどうかを判定すれば条件を満たす長方形かどうかがわかるので、条件を満たすうち最小の長方形を探せばよい。ということもすぐにわかる。
しかし、この方針ではO(N⁵)であり、N=50であるから、50⁵ = 312500000であり、10⁸程度の計算量となる。
10⁸はループの中身がよほどシンプルでない限り間に合わないとどこかで見た(ググったらソースは蟻本らしい)ので、それに3倍の定数倍がかかっていれば間に合わないような気がしてしまう。
その後座標をx,yでソートしてK個取ったり迷走して終了。

正しい方針

上記の前半部分

得られた知見

・10⁸は通らないとか言いつつ条件を満たす点の個数を数えるくらいなら50⁵でも間に合うので、10⁸解が思いついても捨てない。
・端点や端となる辺を与えられた頂点に重なるようにするとうまくいくことが多い。

解くのに必要な要素

・全探索
・最適ケースは端点や端となる辺を条件を満たすギリギリまで厳しくしたものであることがある。
・10⁸解を捨てない強い心

周辺調査によって得られた知見

・長方形の内部に含まれる点の総数は二次元累積和で事前計算O(N²)クエリ回答O(1)で求められる。