AOJ 0254 Scone

問題

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で最大になるっぽいことが分かる.

(加筆の予定は未定です)