The Number of Windows [ AIZU ONLINE JUDGE DSL_3_C ]

judge.u-aizu.ac.jp

問題

長さ N の数列と整数 X（※Long型）が与えられる。
数列の部分列のうち、和が X 以下であるようなものの個数を求めよ。

考察

しゃくとり法の問題です。例によって詳細は省略します。

今回は自分で一から実装するのではなく、以下のページの尺取法テンプレを使って解いてみました。

qiita.com

最初、

・res (以下のコードでは count） += R - L

の部分の意味が分からなかったのですが、

・あるLについて、そのLを起点とした最長区間が求まった
・その最長区間の中に、Lを起点とした部分列は何個あるか？
・（最長区間の長さ）個ある

ということだったんですね。

例えば、和が 10 以下という条件のもとで、L = 1 のとき

・1, 2, 3, 4

という最長区間が求まったとします。このとき、L = 1 を起点とした部分列がこの中に何個あるかというと、

・1
・1, 2
・1, 2, 3
・1, 2, 3, 4

の4つです。したがって、count に 4（区間の長さ） を加算して、次の L へ移る、という処理だったんですね～。

コード

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

	int n = in.nextInt(), q = in.nextInt();
	int[] a = in.nextIntArray(n);

	for (int i=0; i<q; i++) {

		long x = in.nextLong();
		int R = 0;
		long sum = 0;
		long count = 0;

		for (int L=0; L<n; L++) {

			while (R < n && sum + a[R] <= x) {
				sum += a[R];
				R++;
			}

			//あるLについて、Rの最大値が求まった。このとき、Lを起点とした区間は何個存在するか？
			//当然、区間の長さぶんだけ存在する。その意味での count += R-L らしい。
			count += R - L;

			if (R == L) R++;
			else sum -= a[L];

		}

		out.println(count);

	}

}
||<