区間の積

今回は paiza の「区間の積」の問題に挑戦！
前に解き忘れていたっぽい(´;ω;｀)

問題概要

与えられるもの

• 数列の長さ N
• 整数 K
• 長さ N の数列 A

求めるもの

• 数列 A から
  連続した 1 個以上の要素を取り出した部分列のうち、
• 要素の積が K 以上になるもの
• の中での 最短の長さ

入力例1:
5 1
1 1 1 1 1

出力例1:
1


入力例2:
6 16
2 0 2 2 2 2

出力例2:
4

✅OK例：

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

const lines = [];

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

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

    // 区間の積を計算する関数
    function calcProduct(arr) {
        let product = 1;
        for (const v of arr) {
            product *= v;
        }
        return product;
    }

    let ans = Infinity; // 最短長
    let left = 0;       // 区間の左端
    let right = 0;      // 区間の右端

    // しゃくとり法
    while (true) {
        // これ以上区間を伸ばせない or 壊れている場合は終了
        if (right >= N || left > right) {
            break;
        }

        // 現在の区間 [left, right] の積が K 以上
        if (calcProduct(A.slice(left, right+1)) >= K) {
            ans = Math.min(ans, right - left + 1); // 答えを更新または保持
            left++; // 条件を満たすので左を縮める
        }
        // right が 0 の場合は、この区間では絶対に条件を満たさない
        else if (A[right] === 0) {
            left = right + 1; // 末尾（左端）を 0 の次の要素まで動かす
            right++;
        }
        // まだ条件未達なので右を伸ばす
        else {
            right++;
        }
    }

    // 答えを出力
    console.log(ans);
});

🔍 コードの流れ

• 入力から
  • 要素数 N
  • 目標値 K
  • 数列 A
    を受け取る
• left と right を使って
  連続区間 [left, right] を管理する
  （しゃくとり法）
• ループを開始し、以下を繰り返す
• 終了条件チェック
  • right が配列の末尾を超えた
  • または left > right になった
    → ループ終了
• 現在の区間の積を計算
  • A[left] 〜 A[right] の積を求める
• 積が K 以上の場合
  • この区間は条件を満たす
  • 区間の長さで最短を更新
  • より短くできるか試すため
    → left を右へ 1 つ動かす
• 積が K 未満 ＆ A[right] === 0 の場合
  • 区間に 0 が含まれる
  • この区間では条件を満たせない
  • left を right + 1 に移動して
    → 区間をリセット
  • right を 1 つ進める
• それ以外（積が K 未満で 0 ではない）
  • まだ条件未達
  • right を右へ動かし
    → 区間を広げる
• ループ終了後
  • 求めた最短長 ans を出力

📝 まとめ

• 「最短の連続区間」→ しゃくとり法が有効
• 条件を満たしたら 左を縮める
• 条件未達なら 右を伸ばす
• 0 は区間を壊す特別な値 → 扱いに注意