いもす法を用いて計算量をO(N^2)からO(N)に減らす

いもす法について整理します。

問題

AtCoder ABC 014 C

C: AtColor - AtCoder Beginner Contest 014 | AtCoder

ソースコード

解説

まずは普通の解き方を見てみる。

いもす法使わない解法

これは、それぞれのアンケートに対して、その解答で得られた範囲の分だけループによって愚直にカウントしていく方法。

これだと、ループが２重になっているため最悪の計算量がO(N²)となる。今回のNの最大値は10⁶のため解けない。 そこで「いもす法」という手法を用いることで計算量を大幅に減らす方法を試みる。

いもす法を用いた解法

いもす法の手順は以下の通りだ。

1. Nに対応した配列arrを用意する
2. アンケートそれぞれのaからbの範囲(a, b)に対して以下の処理を行う
   arr[a] = +1
arr[b + 1] = -1
3. 全ての要素をチェック後に累積和を取る

累積和とは第N項の値を第０項から第(N-1)項までの和にすることである。

この解法により計算量はO(N)まで減らす事ができるようになる。