2次元いもすをしてみた

2次元平面で異なるN個の範囲を示す座標が与えられ、その重なりがもっとも多い部分を求めるような問題。

普通の解法であれば二次元の配列を用意していN個それぞれについて指定された範囲の数値をインクリメントする事になる。

しかし、二次元平面の縦と横の長さをH,Wとするとこの方法の最悪計算量はO(NWH)であり、Nやら二次元平面の縦横の値が大きくなるとTLEしてしまう。

そこで、いもす法というアルゴリズムを用いてこの数え上げをO(N + WH)で行うことを試みる。いもす法は当然1次元でも使用でき、2次元以上の多次元においても適用できるが、今回はわかりやすくて威力を感じられる二次元を選択することにした。

操作の概要としては
1. 左上、右下に+1を、右上と左下に-1をかく
2. 左から右へ書いてある値を足していく
3. 同様に上から下へ書いてある値を足していく

このようにすることで全範囲の累積値が簡単に求まる。WH回のインクリメント操作がたった4回で済むので大きく計算量が落ちる。

ただ、はじめの説明にある+1と-1の場所に少し注意。下の写真に示したように-1を加える場所は右上の角の一つ右、左下の角の1つ下となる。右下に+1するものはx,yともに一つずらした場所となる。このようにすることで左と上から累積和を求めた時に正しく結果が求まるようになる。
f:id:yuji9511yuji:20181010230736p:plain