しゃくとり法を使う問題は、2種類に分けられます。
たとえば、1.の問題には「ある数列の連続する部分列の和が$K$以下となるもののうち、最長の長さはいくつか」などがあり、2.の問題には「ある数列の連続する部分列の和が$K$以上となるもののうち、最も短い部分列の長さはいくつか」などがあります。
以下のテンプレートは、1.の問題に使えるものです。
T acc = e; // 蓄積値。eは単位元のようなもの
for (int l = 0, r = 0; l < N; ) {
while (r < N && /* accを更新しても条件を満たすか */) {
/* accを更新してからr++ */
}
/* 区間[l, r)が条件を満たす範囲 */
/* accを更新してからl++ */
// この行は思考停止しながら書く
if (l >= r) r = l, acc = e;
}
実装の方針としては、半開区間で実装しています。たとえば、上のテンプレートの7行目では、`acc`は区間$[l, r)$の値を保持しています。条件を満たす部分列の長さは$r-l$で取得できます。
続けて2.のテンプレートも載せます。
T acc = e; // 蓄積値。eは単位元のようなもの
for (int l = 0, r = 0; l < N; ) {
while (r < N && /* accを更新しても条件を満たさないか */) {
/* accを更新してからr++ */
}
/* 条件を満たさない状態で最後までたどり着いた */
if (r == N) break;
/* 区間[l, r + 1)が条件を満たす範囲 */
/* accを更新してからl++ */
// この行は思考停止しながら書く
if (l >= r) r = l, acc = e;
}
1.のテンプレートに`if (r == N) break;`が加わっただけです。あとは1.と同じ感覚で実装できます。ただ、ひとつ気をつけなければいけない点があり、9行目の`acc`は「ぎりぎり条件を満たさない値」を持っているという点です。ということで、条件を満たす値を作るために、`acc`と`r`を使う必要があります。
| 問題 | 実装 |
|---|---|
| AOJ Course The Number of Windows | ソースコードへのリンク。`acc`は整数型、`e`は$0$とします。 |
| POJ 3061 Subsequence | POJでは実装を公開できないので、ページ下に掲載します。 |
| AtCoder ABC032 C - 列 | ソースコードへのリンク。`acc`は整数型、`e`は$1$とします。 |
| AtCoder ABC038 C - 単調増加 | ソースコードへのリンク。`acc`は直前の数字、`e`は$0$とします。 |
| AtCoder ARC022 B - 細長いお菓子 | ソースコードへのリンク。`acc`は`set`、`e`は`{}`とします。 |
| AtCoder ABC098 D - Xor Sum 2 | ソースコードへのリンク。`acc`が複数あるパターンです。 |
POJ 3061 Subsequence以外の問題はすべて、1.のテンプレートに当てはめることができます。
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
typedef long long i64;
typedef vector<i64> vi64;
int main() {
int Q; cin >> Q;
rep(i, Q) {
int N, S; cin >> N >> S;
vi64 a(N); rep(i, N) cin >> a[i];
int ans = N + 1;
i64 sum = 0;
for (int l = 0, r = 0; l < N; ) {
while (r < N && sum + a[r] < S) {
sum += a[r++];
}
if (r == N) break;
ans = min(ans, r - l + 1);
sum -= a[l++];
if (l >= r) r = l, sum = 0;
}
if (ans == N + 1) cout << 0 << endl;
else cout << ans << endl;
}
return 0;
}
こちらがPOJ 3061 Subsequenceの実装です。`acc`は整数型、`e`は$0$です。2.の問題なので、`if (r == N) break;`という行があります。条件を満たす数列の長さは$r - l + 1$です。$r - l$でない理由は、$r - l$は「ぎりぎり条件を満たさない数列の長さ」だからです。$1$を足すことで、条件を満たす数列の長さになります。