1 次元上のいもす法 1 (paizaランク C 相当)

(はじめに)

この問題では、累積和のアルゴリズムを応用した「いもす法」について扱います。

累積和といもす法の簡単な説明は以下の通りです。

・ 累積和

ある点（最初や最後）からの累積和を考えることで、複数の区間の値を高速に求めることができる。
区間の値に更新が起きる場合にはあまり適さない。

・ いもす法

区間の値を何度も更新し、最後にそれぞれの値を得たい場合に有効である。

先に区間の入口と出口のみに加算と減算をおこなったあと累積和をとることで最後にまとめて全体の任意の値を求めることができる。

いもす法も累積和と同じく、前処理をおこなうことで大幅に計算量を減らすことができるアルゴリズムです。この問題集を通していもす法の問題に触れ、少しずついもす法に慣れていきましょう。

まずは、問題を見てみましょう。

---

(問題)

横に並んだ 10 個のマスがあり、最初、マスには全て 0 が書かれています。

以下の 5 つの範囲が与えられます。それぞれの範囲に対して、その範囲に含まれるマスに 1 を加算していきます。

すべての加算が終わった時点での 10 個のマスに書かれた値のうち、最大の値をいもす法を用いて求めてください。

1 マス目から 3 マス目
1 マス目から 8 マス目
3 マス目から 8 マス目
3 マス目から 6 マス目
7 マス目から 9 マス目

---

(ヒント : いもす法の考え方)

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

問題文通りに実装する場合、範囲の左端から右端に 1 を足す動作を繰り返せばよいですが、そのようにやってしまうと、マスの長さや範囲の長さがとても大きい値になった場合に、毎回の計算量が多くなってしまい、処理に時間がかかってしまいます。

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

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

最初、10 個のマスは全て 0 です。

0 0 0 0 0 0 0 0 0 0

いもす法では、範囲が与えられたとき、まずその範囲の入口に 1 を加算し、出口から 1 を減算します。範囲の入口とは、範囲の左端のマスを、範囲の出口とは、範囲の右端 + 1 番目のマス (その範囲から出た直後のマス) を指します。

例えば、1 マス目から 3 マス目のマスに 1 を加算したいとき、1 マス目に 1 を加算し、4 マス目に 1 を減算します。

1 0 0 -1 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

となり、1 マス目から 3 マス目までに 1 を加算することができているとわかります。

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

1 マス目から 6 マス目
3 マス目から 9 マス目
4 マス目から 5 マス目

これらの範囲の入口に加算、出口に減算をおこなうと以下のようになります。

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

そしてこれに累積和をとると

1 1 2 3 3 2 1 1 1 0

となり、最大値が 3 であることがわかります。

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