列 [ AtCoder Beginner Contest 032 C ]

atcoder.jp

問題

長さ N の数列と整数 K が与えられる。
積が K 以下であるような数列の部分列のうち、最も長いものの長さを出力せよ。

考察

しゃくとり法の典型問題……ということで何とか自力で考察・実装しました。

・積が K より大きい　→　左端を伸ばす
・積が K 以下？　→　右端を伸ばす

という手順で区間を更新していきますが、実際にはもっと細かく条件設定しなければなりません。

ループの条件
・左端が「区間の右端」に到達するまで回す

左端を伸ばす条件
・左端と右端が同じ位置にない場合、かつ
　・積が K より大きい、もしくは右端が「区間の右端」にある場合

右端を伸ばす条件
・左端と右端が同じ位置にある場合、あるいは
　・積が K 以下、かつ右端が「区間の右端」にない場合

他の人の提出コードを見たら、while ループではなく for ループを使っている人がほとんどだったので驚きました。while ループのほうは「左端と右端を同時並行的に伸ばしていく」、for ループのほうは「左端毎に、右端を可能な限り伸ばす」というイメージでしょうか。

コード

void solve (FastScanner in, PrintWriter out, Methods ms) {
	
	//入力
	int n = in.nextInt(), k = in.nextInt();
	int[] a = new int[n];
	
	//配列に格納しつつ、例外処理をする
	for (int i=0; i<n; i++) {
		a[i] = in.nextInt();
		if (a[i] == 0) {
			out.println(n);
			return;
		}
	}
	
	int L = 0, R = 1;
	long sum = a[0];
	int max = sum<=k? 1 : 0;
	
	//しゃくとり法
	while (L < n) {

		if (L != R && (sum > k || R == n)) {
			sum /= a[L];
			L++;
		}
		else if (L == R || (sum <= k && R != n)) {
			sum *= a[R];
			R++;
		}

		if (sum <= k) max = Math.max(max, R - L);

	}

	out.println(max);

}