2 次元上のいもす法 1 PHP編（paizaランク C 相当）

5 行 5 列のマスがあり、最初、マスには全て 0 が書かれています。

x 座標を列、y 座標を行とします。以下に

(左上の x 座標, 左上の y 座標) (右下の x 座標, 右下の y 座標)
(1 ≦ x ≦ 5, 1 ≦ y ≦ 5)

という形で、マスに沿った長方形の 5 つの範囲が与えられます。それぞれの範囲に対して、その範囲に含まれるマスに 1 を加算していきます。

5 行 5 列のマスに書かれた値のうち、最大の値をいもす法を用いて求めてください。

(1, 1) (3, 3)
(2, 2) (4, 4)
(3, 3) (5, 5)
(1, 3) (3, 5)
(3, 1) (5, 3)

---

(ヒント)

ループを用いてそれぞれの範囲に 1 を足していけば、いもす法を使わずとも答えを求めることができますが、練習としていもす法で解いてみましょう

問題文通りに実装する場合、範囲内のすべての整数に 1 を足す動作を繰り返せばよいですが、そのようにやってしまうと、マスの長さや範囲の長さがとても大きい値になった場合に、計算量が多く対応することができません。

そこで、適切な前処理をしていもす法を用いることで、答えを求める際の計算時間を大きく短縮することができます。

実際に考えてみましょう。

最初、5 行 5 列のマスは全て 0 です。

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

2 次元の場合も 1 次元の場合と変わらず、範囲の始まりと終わりに加減算をおこないます。

加算するマス : 範囲の左上のマスと、範囲の右下の 1 つ右、かつ 1 つ下のマス

減算するマス : 範囲の右上の右隣のマス、範囲の左下の直下のマス、つまり範囲から 1 マス出たマス

例えば、左上が (1, 1), 右下が (3, 3) の長方形の範囲にそれぞれ 1 を加算したいとき、(1, 1), (4, 4) に 1 を加算し、(1, 4), (4, 1) から 1 を減算します。

 1 0 0 -1 0
 0 0 0  0 0
 0 0 0  0 0
-1 0 0  1 0
 0 0 0  0 0

そして、全ての範囲の入口と出口にそれぞれ加算と減算をおこなった後、全てのマスの値をそれぞれ求めるために、横方向と縦方向のそれぞれで累積和をとります。

例えば

 1 0 0 -1 0
 0 0 0  0 0
 0 0 0  0 0
-1 0 0  1 0
 0 0 0  0 0

に対して横方向の累積和をとると以下のようになります。

 1  1  1 0 0
 0  0  0 0 0
 0  0  0 0 0
-1 -1 -1 0 0
 0  0  0 0 0

そこからさらに、縦方向の累積和をとると、以下のようになります

1 1 1 0 0
1 1 1 0 0
1 1 1 0 0
0 0 0 0 0
0 0 0 0 0

このようにして、(1, 1) から (3, 3) に 1 を加算することができました。

また、縦方向の累積和をとったあとに、横方向の累積和をとっても同様の結果を得ることができます。

例として、以下の 2 つの範囲にそれぞれ 1 を加算したときの最大値を求めてみましょう。

(1, 1) (4, 4)
(2, 2) (5, 5)

これらの範囲のそれぞれ入口と出口に加減算をおこなうと以下のようになります。
注意として、マスを 6 × 6 と拡張して考えています。

これは、2 つ目の範囲の右下が (5, 5) なので、加減算するマスの座標が (6, 6) や(1, 6), (6, 1) を取ることになるためです。

 1  0 0 0 -1  0
 0  1 0 0  0 -1
 0  0 0 0  0  0
 0  0 0 0  0  0
-1  0 0 0  1  0
 0 -1 0 0  0  1

これに横方向の累積和をとると以下のようになります。

 1  1  1  1  0 0
 0  1  1  1  1 0
 0  0  0  0  0 0
 0  0  0  0  0 0
-1 -1 -1 -1  0 0
 0 -1 -1 -1 -1 0

さらに縦方向の累積和をとると、以下のようになります。

1 1 1 1 0 0
1 2 2 2 1 0
1 2 2 2 1 0
1 2 2 2 1 0
0 1 1 1 1 0
0 0 0 0 0 0

したがって、最大値が 2 であることがわかります。

今回の問題を解くには、まず 5 つの範囲が与えられているので、それぞれの範囲にたいして加減算をおこないます。その後、縦方向と横方向で累積和を求めたのち、最大値を求めることで解くことができます。