No.032 D

モンスター $i$ のこうげき力を $x_i$, ぼうぎょ力を $y_i$ とする.

$K$ 個のモンスターについてこうげき力とぼうぎょ力を $xy$ 平面上にプロットすると, 不安定度はモンスターの点をぴったりすべて収めることができる辺が軸に平行な長方形の長辺の長さとなる.

逆に一辺が $w$ の正方形内に $K$ 個以上のモンスターの点を入れることができれば, $K$ 個のモンスターの最小の不安定度は $w$ 以下である.

まずはこれを利用して最小の不安定度を求める.

一辺が $w$ の正方形を左下の位置で全探索して正方形内に $K$ 個以上のモンスターの点を入れられる正方形の位置がひとつでもあるかを調べる. 左下からのモンスターの数の累積和をあらかじめ計算しておけばこれは高速に計算できる.

そして $w$ を二分探索で探す.

$w$ が決まったので続いては組み合わせの数である.

正方形の右下が $(x, y)$ になったときに重複なく数えられるパターンは以下の通りである.

• 右下にモンスターの点がある.
• 正方形の左辺または下辺上にモンスターの点がある.

正方形内のモンスターの点の数を $s$, 右下のモンスターの点の数を $t$, 左辺上のモンスターの点の数を $u$, 下辺上のモンスターの点の数を $v$ とすると, 組み合わせの数は以下のようになる.

• $${}_sC_K - {}_tC_K$$
• $${}_{s-t}C_k - {}_{s-t-u}C_K - {}_{s-t-v}C_K + {}_{s-t-(u+v)}C_K$$

階乗と逆元はあらかじめ計算しておく.

これをすべての $(x, y)$ について足せば組み合わせの数となる.