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

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

問題

AtCoder ABC 014 C

C: AtColor - AtCoder Beginner Contest 014 | AtCoder

ソースコード

解説

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

いもす法使わない解法

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

f:id:atiek1121:20161112114452p:plain

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

いもす法を用いた解法

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

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

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

f:id:atiek1121:20161113092036p:plain

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