AOJ 0254 Scone

問題

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

問題概要

数列 {a_n} と整数 M が与えられる．
適当な i <= j を選んで ( a(i) + a(i+1) + ... + a(j) ) mod M を最大化せよ．

・制約
1 <= n <= 30000
1 <= M <= 100000
0 <= a(i) <= 2^32 - 1

解法

累積和と二分探索．
mod を取った累積和を sum(i) で表すことにする．
右端 j を固定すると，j までの累積和の中で sum(j) 以上で最小のもの sum(i) を見つけて， ( sum(j) - sum(i) + M ) mod M を見ていけば良い．
sum(i) を見つけるのに二分探索する．setにつっこめば楽．

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, m;
    while(cin >> n >> m, n) {
        vector<int> a(n+1);
        for(int i=1; i<=n; ++i) {
            cin >> a[i];
            a[i] %= m;
            (a[i] += a[i-1]) %= m;
        }
        int res = 0;
        set<int> s;
        for(int i=1; i<=n; ++i) {
            auto it = s.upper_bound(a[i]);
            res = max(res, a[i]);
            if(it != s.end()) {
                res = max(res, (a[i] - *it + m) % m);
            }
            s.insert(a[i]);
        }
        cout << res << endl;
    }
}