3061 Subsequence

3061 Subsequence

N個の数字から成る数列の部分数列で、その和がS以上であるものの内、最小の長さを求める問題。

英文は簡単に読める割にAC率が30％強という問題。

単純に（何も考えずに）やろうとすると、sum[i][j]をi番目の数字を先頭とする長さjの部分数列の和であるとして、
この配列を埋めるのにO(N^2)かかるため10 < N < 100,000よりTLE(?)（そもそもMLEか）

そこで、部分数列の最後の要素に着目する。すると、部分数列の要素数に対して、その和は単調増加することがわかる。

例えばサンプル入力の<5 1 3 5 10 7 4 9 2 8>という数列ならば、5番目の数字10を部分数列の最後の要素としたとき、

長さ1の部分数列<10> の和は5
長さ2の部分数列<5 10> の和は15
長さ3の部分数列<3 5 10> の和は18
長さ4の部分数列<1 3 5 10> の和は19
長さ5の部分数列<5 1 3 5 10>の和は24

となる。

よって二分探索が使える（はじめての二分探索！）

N個の各数字を部分数列の最後の要素とする場合について二分探索を行うので、オーダーはN*logNになる。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<climits>

using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
	int N, S;
	scanf("%d %d", &N, &S);
	int seq[N+1];
	int sum[N+1];
	memset(sum, 0, sizeof(sum));
	for (int i = 1; i <= N; ++i) {
	    scanf("%d", &seq[i]);
	    sum[i] = sum[i-1] + seq[i];
	}
	int ans = INT_MAX;
	for (int i = N; i >= 1; --i) {
	    int f = 1;
	    int b = i;
	    while (true) {
		if (sum[i] - sum[i-(f+b)/2] >= S) {
		    ans = min(ans, (f+b)/2);
		    b = (f+b)/2;
		} else {
		    f = (f+b)/2;
		}
		if (b-f <= 1) break;
	    }
	}
	if (ans == INT_MAX) printf("0\n");
	else printf("%d\n", ans);
    }
}

0出力のパターンを失念していてWA連発した

[追記]
TLEに陥る版。実際にsum[N][N]を確保する必要はないからMLEにはならないが、O(N*N)でやっぱりTLEだった。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<climits>

using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
	int N, S;
	scanf("%d %d", &N, &S);
	int seq[N+1];
	int sum[N+1];
	memset(sum, 0, sizeof(sum));
	for (int i = 1; i <= N; ++i) {
	    scanf("%d", &seq[i]);
	    sum[i] = sum[i-1] + seq[i];
	}
	bool ok = false;
	for (int i = 1; i <= N; ++i) {
	    for (int j = 1; j <= N+1-i; ++j) {
		if (sum[i+j-1] - sum[j-1] >= S) {
		    printf("%d\n", i);
		    ok = true;
		    break;
		}
	    }
	    if (ok) break;
	}
	if (!ok) printf("0\n");
    }
}