ABC 075

グラフ理論での「橋」の数を見つける。たとえ話などが使われていない、直接的な問題。

橋の見つけ方やその図は、橋（bridge）検出アルゴリズム - nupiocaの日記が詳しい。 一から実装しようとするとちょっと難しいが、このアルゴリズムを使うとグラフが大きくなっても十分に速く解を求められる。

でも、今回はノード数・リンク数の制約がとても少ないため、リンクを1本ずつ抜いて連結か調べる、というやり方でも十分間に合った。制約から計算量を見積もれるかが大事だったようだ。

以下は、検出アルゴリズムを用いての回答。

N個の点が2次元座標にばらまかれている。K個以上の点を含む最小の長方形（辺はX,Y軸に平行）の面積を求める。辺上にある点は長方形に含まれるとする。

座標圧縮＋二次元累積和。

答えとなる長方形の4つの各辺上には必ず点がある。無ければ点の位置まで縮小した方が面積が小さくなるからである。 そのため、4辺の位置の組み合わせを総当たりで試し、中にK個以上の点があるような組み合わせの中での面積の最小値を求めればよい。 Nの上限が50と小さいので、解ける。

各点のX座標、Y座標を小さい順にソートしておくと、探索範囲を限定できる。

たとえば長方形の左縦辺（X座標が小さい方）に、小さい方からi番目の値を用いるとする。すると、K個の点を含めなければならない時、右縦辺はi+K-1番目以降を調べればよい。それより小さい値では、間にK個の点がそもそも存在しない。

また、3辺を固定して最後の1辺を小さい方から順に探索する時、ある長方形に含まれる点がK個を超えたら、そこで最後の1辺の探索は打ち切ってよい。 それ以上探索を続けても、面積が広がるだけ。

二次元空間のマス目や格子点に値が振られているとき、原点から点(x1, y1)までの長方形に含まれる値の和を配列 a[x1][y1] に記録したものを二次元累積和という。

┌─────┐
│        ・│   1 2 3 4 5
│  ・      │   1 2 3 4 4
│・        │→ 1 1 2 3 3
│    ・    │   0 0 1 2 2
│      ・  │   0 0 0 1 1
└─────┘

今回は点の数を記録しておけばよい。x,yが小さい方から逐次的に以下で計算できる。

$a[x][y] = a[x - 1][y] + a[x][y - 1] - a[x - 1][y - 1] +$ (x, y)に点が存在する場合1

ここから左下(x1, y1)、右上(x2, y2)の長方形に含まれる点の数を求める場合は、以下で計算できる。

$a[x2][y2] - a[x2][y1 - 1] - a[x1 - 1][y2] + a[x1 - 1][y1 - 1]$

座標圧縮した上でこれを事前計算すれば、繰り返し必要になる、長方形に含まれる点の個数計算がO(N)からO(1)になる。

（ただし、今回のように制約が小さい場合、省略できるコストより作成コストの方が上回るため、却って遅くなる）