読者です 読者をやめる 読者になる 読者になる

AOJ 0270 Modular Query モジュロ・クエリ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0270

カードが6, 7, 11, 13, 14, 15, 16, 19で,q=5のクエリに答えたいとする。

5で割った余りが最大になり得るのは,5*1のlower_boundの1つ前,5*2のlower_boundの1つ前,……,なので,ソートしておいて二分探索する方法,set.lower_boundを使う方法,累積和的な方法などで調べられる (下の図の例のように「5*1のlower_boundの1つ前」の要素が無い場合もあるので注意する)。

f:id:kujira16:20150823132241p:plain

この方法を使ったときの1クエリあたりの計算量を考えると,二分探索的な方法ではO(log N)の探索をceil(N/q)回,累積和的な方法ではO(1)の探索をceil(N/q)回行うことになる。クエリは105個まで与えられるので,これでは間に合わないような気がしてしまうが,ここで「同じ数を 2 回以上質問することはありません」という条件が活用できないか考えてみよう.

ceil(N/q)はqが小さいほど大きくなるので,最悪ケースとしてクエリqが1〜Qの整数それぞれ1つずつだった場合を考える。探索に二分探索的な方法を使ったとして,計算量は以下のようになる。

{\displaystyle
\sum_{q=1}^Q \frac{N}{q} \log N=N\log N \sum_{q=1}^Q \frac{1}{q}
}

ここで,\displaystyle\sum_{q=1}^Q \frac{1}{q} は調和数と呼ばれており,だいたい \ln Q くらいに漸近する。

調和数 (発散列) - Wikipedia

よって,全体的な計算量も O(N \log N \log Q) 程度に収まる。N=3*105とQ=105を代入してみると,6*107くらいになりこれでも時間内に収まるが,不安なら二分探索的な方法ではなく累積和的な方法を使ってlog Nの項を消すと良いかもしれない。