問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0254
概要:N個の正整数列 (1 <= N <= 3*104) が与えられる。連続する部分列の和 mod M (1 <= M <= 105) を最大化したときの値を求めよ。
O(N3) 解法
[begin,end) をO(N2)で決めて,和のmod MをO(N)で計算する。
O(N2) 解法
累積和テーブルpsumを前もってO(N)で構築しておくと,和のmod Mが(psum[end] - psum[begin] + M) % M
みたいな感じでO(1)で計算できる。
[begin,end) をO(N2)で決めて,和のmod MをO(1)で計算する。
O(N log N) 解法
[begin, end) のendをO(N)で決めて,和のmod Mを最大にするようなbeginを二分探索で求める。
例えば,スコーンの数が1,7,2,12,2,1,6,2でM=5であったとする.先頭からの累積和,先頭からの累積和のmod Mを求めて表にすると,以下のようになる.
スコーンの数 | - | 1 | 7 | 2 | 12 | 2 | 1 | 6 | 2 |
累積和 | 0 | 1 | 8 | 10 | 22 | 24 | 25 | 31 | 33 |
累積和 mod M | 0 | 1 | 3 | 0 | 2 | 4 | 0 | 1 | 3 |
end=8 (スコーンの数=2, 累積和=33, 累積和 mod M=3のところまでを足す) と固定して,beginを変えて実験してみると,beginまでの累積和のmod Mがset([0,1,3,0,2,4,0,1]).upper_bound(3)=4
のときに[begin,end)の和のmod Mが(3 - 4 + M) % M = 4
で最大になるっぽいことが分かる.
(加筆の予定は未定です)