最長の区間（しゃくとり法）

今回は paiza の「最長の区間」の問題に挑戦！

🧩 問題概要

🔹 入力で与えられるもの

• N：数列 A の長さ
• M：区間和の上限値
• 数列 A = [A₀, A₁, …, Aₙ₋₁]

🔹 何を求める問題か

• 数列 A の中から連続した部分列（区間） を 1 つ選ぶ
• その区間の 要素の和が M を超えない という条件で、
• 長さ（要素数）が最大 になる区間の長さを求める

🔹 「部分列」の重要ポイント

• 必ず連続している
• 1 要素だけの区間も OK
• 空区間は考えない

🔹 出力

• 条件を満たす区間の 最大の長さ
• 1 行で出力
  
  
  

入力例：

10 27
16 9 2 6 18 3 1 3 6 8

出力例：

5

✅OK例：

const rl = require('readline').createInterface({
    input: process.stdin,
    output: process.stdout
});

const lines = [];

rl.on('line', (line) => lines.push(line));

rl.on('close', () => {
    // N: 要素数, M: 区間和の上限
    const [N, M] = lines[0].split(' ').map(Number);
    // 数列 A
    const arrA = lines[1].split(' ').map(Number);

    let left = 0;   // 区間の左端
    let rangeSum = 0;    // 現在の区間和
    let ans = 0;    // 条件を満たす最大長

    // 右端を1つずつ伸ばす
    for (let right = 0; right < N; right++) {
        rangeSum += arrA[right]; // 右端を追加

        // 和が M を超えたら左端を縮める
        while (rangeSum > M) {
            rangeSum -= arrA[left];
            left++;
        }

        // 条件を満たす区間の長さを更新
        ans = Math.max(ans, right - left + 1);
    }

    // 出力
    console.log(ans);
});

🔍 このコードの流れ

• 入力から
  • 配列の長さ N
  • 上限値 M
  • 数列 arrA
    を受け取る
• left = 0
  → 区間の左端を 0 に初期化
• right を 0 → N-1 まで 1 つずつ動かす
  → 区間の右端を伸ばす
• arrA[right] を rangeSum に足す
  → 区間に要素を追加
• 区間和が M を超えている間（条件を満たしていない）
  • arrA[left] を引く
  • left を右へ進める
    → 区間を縮める
• 区間和が M 以下になったら
  • right - left + 1 を計算
  • 最大値 ans を更新
• すべての right について処理が終わったら
  • ans を出力する

✅OK例 2：

const rl = require('readline').createInterface({
    input: process.stdin,
    output: process.stdout
});

const lines = [];

rl.on('line', (line) => lines.push(line));

rl.on('close', () => {
    // N: 配列の長さ, M: 区間和の上限
    const [N, M] = lines[0].split(' ').map(Number);
    // 数列 A
    const arrA = lines[1].split(' ').map(Number);

    let head = 0; // 区間の右端（含まない: 次に入れる予定の位置）
    let tail = 0; // 区間の左端
    let rangeSum = 0;  // 現在の区間和
    let ans = 0; // 条件を満たす最大長

    // しゃくとり法
    while (true) {
        if (rangeSum <= M) {
            // 条件を満たしているので答えを更新し、右端を伸ばす
            ans = Math.max(ans, head - tail);
            if (head === N) break;

            rangeSum += arrA[head];
            head++;
        } else {
            // 条件オーバーなので左端を縮める
            rangeSum -= arrA[tail];
            tail++;
        }
    }

    // 出力
    console.log(ans);
});

🔍 このコードの流れ

• 入力から
  • 配列の長さ N
  • 上限値 M
  • 数列 arrA
    を受け取る
• head = 0, tail = 0→ 区間を空の状態[tail, head)` で初期化
• rangeSum = 0
  → 区間和を 0 でスタート
• while (true) で区間を動かし続ける
• rangeSum <= M のとき（条件〇）
  • 現在の区間長 head - tail + 1 で ans を更新
  • まだ右に伸ばせるなら
    • arrA[head] を足す
    • head を 1 進める
  • head === N なら終了
• rangeSum > M のとき（条件✕）
  • arrA[tail] を引く
  • tail を 1 進めて区間を縮める
• 右端が最後まで到達したらループ終了
• ans を出力する

📝まとめ

• 区間を [left, right] または [tail, head) として管理
• 処理の流れは常に同じ：
  • 右を伸ばす → 和が大きくなる
  • 条件オーバー → 左を縮める
  • 条件OK → 長さを更新
• 条件を満たす間は右を伸ばし、超えたら左を縮め、最大長を記録する。