ぐっすり [ AtCoder Regular Contest 036 A ]

atcoder.jp

問題

長さ N の数列がある。
数列の長さ 3 の部分列のうち、初めて和が K 未満になるような部分列の位置を求めよ。

考察

勉強のため、二種類の解法で解きたいと思います。

累積和から部分和を求める

数列に対してあらかじめ累積和をとっておくことで、その数列の好きな位置・好きな長さの部分和を O(1) で求められるようになるテクニックです。以下のサイトで詳しく解説されています。

satanic0258.hatenablog.com

コード（累積和から部分和を求める）

void solve (FastScanner in, PrintWriter out, Methods ms) {

	int n = in.nextInt(), lower = in.nextInt();
	
	long[] sum = new long[n+1];
	sum[0] = 0;
	for (int i=1; i<n+1; i++) {
		sum[i] = sum[i-1] + in.nextInt();
	}
	
	for (int i=3; i<n+1; i++) {
		if (sum[i] - sum[i-3] < lower) {
			out.println(i);
			return;
		}
	}
	
	out.println(-1);

}

しゃくとり法

詳しくは以下略。
長さが常に一定（3）のしゃくとり法なので、実装が異様に簡単です。

コード（しゃくとり法）

void solve (FastScanner in, PrintWriter out, Methods ms) {

	int n = in.nextInt(), lower = in.nextInt();
	int[] ar = in.nextIntArray(n);
	
	int L = 0, R = 3;
	int sum = ar[0] + ar[1] + ar[2];
	
	while (L < n-3) {
		if (sum < lower) {
			out.println(R);
			return;
		}
		R++;
		sum += ar[R-1];
		sum -= ar[L];
		L++;
	}
	
	out.println(-1);
	
}

ちなみに

N<=10^5 なので、部分列の和を毎回求める全探索（a[0]+a[1]+a[2], a[1]+a[2]+a[3]......）でも間に合います。
部分列の長さが短いので、全探索としゃくとり法の計算量の差がほとんどありませんね……。