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

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

新しいアルゴリズムを学んだ！

🧩 問題概要

🔹 入力内容

• 整数 N：数列の長さ
• 整数 M：目標となる合計値
• 数列 A = [A₁, A₂, …, Aₙ]

🔹 何を求める問題か

• 数列 A の中から連続した一部分（部分列） を選ぶ
• その部分列の 要素の合計が M 以上 になるもののうち、
  • 長さ（要素数）が最も短いもの を求める
• 条件を満たす部分列が 1つも存在しない場合 は、-1 を出力

🔹 出力内容

• 条件を満たす 最短の区間の長さ（要素数）
• 存在しなければ -1

入力例:

10 27                  // N M
16 9 2 6 18 3 1 3 6 8  // A

出力例:

3

△ OK例：TLEの懸念

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

const lines = [];

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

rl.on('close', () => {
    const [N, M] = lines[0].split(' ').map(Number);
    const arrA = lines[1].split(' ').map(Number);
    
    const prefixSum = Array(N).fill(0);
    for (let i = 0; i < N; i++) {
        prefixSum[i + 1] = prefixSum[i] + arrA[i];
    }
    
    // 存在しない
    if (prefixSum[N] < M) {
        console.log('-1');
        return;
    }
    
    // 長さ１
    if (arrA.filter(a => a >= M).length > 0) {
        console.log('1');
        return;
    }
    
    // 長さ2以上
    for (let i = 2; i <= N; i++) {
        for (let j = 0; j <= N - i; j++) {
            const rangeSum = prefixSum[j + i] - prefixSum[j];
            if (rangeSum >= M) {
                console.log(i);
                return;
            } 
        }
    }
});

一応テストケースは通過。

✅OK例：しゃくとり法

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

const lines = [];

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

rl.on('close', () => {
    const [N, M] = lines[0].split(' ').map(Number);
    const arrA = lines[1].split(' ').map(Number);

    // しゃくとり法 のための変数
    let left = 0;
    let rangeSum = 0; // 区間和
    let ans = Infinity;

    // しゃくとり法
    for (let right = 0; right < N; right++) {
        rangeSum += arrA[right]; // 右端を足す 

        // 条件を満たしている間、左を縮める
        while (rangeSum >= M) {
            ans = Math.min(ans, right - left + 1); // 答え更新
            rangeSum -= arrA[left]; // 左端を引く
            left++; // 左を縮める
        }
    }

    // 答えを出力
    console.log(ans === Infinity ? -1 : ans);
});

🔍 コードの流れ

• 入力から
  • 配列の長さ N
  • 目標の和 M
  • 数列 arrA を受け取る
• しゃくとり用の変数を初期化
  • left：区間の左端（0からスタート）
  • rangeSum：現在の区間の合計
  • ans：条件を満たす最短長（初期値：Infinity）
• right を 0 から N-1 まで動かす
  • arrA[right] を区間に追加
  • rangeSum を更新する
• rangeSum >= M の間は繰り返す
  • 現在の区間長 right - left + 1 で ans を更新
  • 左端 arrA[left] を区間から除外
  • left を右へ動かして区間を短くする
• 全ての right を試し終えたら
  • 一度も条件を満たさなかった → -1
  • 条件を満たした → 最短長 ans を出力

💡 「しゃくとり法」 まとめ

🔍 基本の考え方

条件を満たす「連続区間」を保ちながら、
その区間を少しずつ動かして最適な答えを探す方法。

🔍 処理の流れ

① 区間を1つ決める

• 最初は空、または最小の区間から始める
• left と right の2つで区間を表す

② 条件をチェックする

• 今の区間が 条件を満たしているか？ を確認する

※ 今回のコードのこの部分：(rangeSum >= M)

③ 条件を満たしている場合

• 今の区間は、
  👉 答えになる可能性がある
• 最短（最長）を狙うために、
  👉 区間をより短く（または長く）する
  （ ※ 今回の場合は、left を右へ動かして短くする（左端を引く）
  → left++; , rangeSum -= arrA[left] ）
• その前に、
  👉 答えを更新しておく ( ans = Math.min(ans, right - left + 1) )

④ 条件を満たしていない場合

• このままでは答えにならない
  👉 区間を広げる（または縮める）
  （ ※ 今回の場合は、right を右へ動かして広げる（右端を足す）
  → for (let right = 0; right < N; right++) { , rangeSum += arrA[right]; ）
• 新しい要素を含めて、条件達成を目指す

⑤ これを繰り返す

• 区間を動かし続ける
• もう右にも左にも動かせなくなったら終了