PCK-2012 問9 - スコーン配達計画

問題文 : スコーン配達計画(pdf注意, 28枚目-30枚目)

解法 :
部分列 mod Mの最大値を求める問題である.
区間[i, j]の和 mod Mをすべて確かめると, 累積和を用いてもO(N^2)となってしまうため、セグメント木を使ってこの計算を高速化する.
i < jとなる(i, j)各組について, sum[j] - sum[i] mod Mが最大となる可能性があるものは, 0 ~ iでsum[i]が最小, またはsum[j] < sum[i]かつsum[i]が最大となるものである.

jについてはループを回し, iについてはRMQで値を求めてやると, O(NlogM)時間でこの問題を解くことが可能となる.
(同様のことがsetなどを用いても可能と考えられる.)

コード :

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int N, M;
int pSeg[1 << 19];

void update(int k, int x)
{
	k += (1 << 18) - 1;
	pSeg[k] = x;
	
	while (k){
		k = (k - 1) / 2;
		pSeg[k] = min(pSeg[k * 2 + 1], pSeg[k * 2 + 2]);
	}
}

int getMin(int a, int b, int k, int l, int r)
{
	if (b <= l || r <= a){
		return (1 << 30);
	}
	
	if (a <= l && r <= b){
		return (pSeg[k]);
	}
	int lch = getMin(a, b, k * 2 + 1, l, (l + r) / 2);
	int rch = getMin(a, b, k * 2 + 2, (l + r) / 2, r);
	
	return (min(lch, rch));
}

int main(void)
{
	static int rSum[100000];
	
	while (1){
		scanf("%d %d", &N, &M);
		
		if (N + M == 0){
			break;
		}
		
		for (int i = 0; i < 1 << 19; i++) pSeg[i] = M;
		memset(rSum, 0, sizeof(rSum));
		
		for (int i = 0; i < N; i++){
			int t;
			scanf("%d", &t);
			rSum[i + 1] = (rSum[i] + (t % M)) % M;
		}
		int ans = 0;
		
		for (int i = 0; i < N; i++){
			update(rSum[i + 1], rSum[i + 1]);
			int lMin = getMin(0, rSum[i + 1], 0, 0, 1 << 18);
			int rMin = getMin(rSum[i + 1] + 1, M, 0, 0, 1 << 18);
			
			ans = max(max(ans, rSum[i + 1]), max(rSum[i + 1] - lMin, (rSum[i + 1] - rMin + M) % M));
		}
		
		printf("%d\n", ans);
	}
	
	return (0);
}