区間の長さ《しゃくとり法》

累積和メニュー

hogeちゃん

2022.09.12

累積和メニュー【区間の長さ 1 〜 4】※しゃくとり法

問題【STEP: 1】区間の長さ 1

Task

10 個の数列において総和が 15 以下の区間の最大の長さを求めてね。

【区間の長さ 1】コード

const A = '1 5 9 1 20 5 3 6 5 4'.split(' ').map(Number);
let [left, right] = [0, 0];  // [区間の左端, 区間の右端]
let sum = 0;  // 区間内の値の和
let area = 0;  // sum が 15 以下の区間の 最も長い部分配列の要素数
while (left < 10 - area) {  // 左端が 要素数 - area より小さい間
  // "right を進められるところまで進める"
   while (right < 10 && sum + A[right] <= 15) { // right が 10 未満で sum + A[right]が 15 以下の間…
      sum += A[right];  // sum に A[right] を加算
      right++;  // 右端を1つ進める
   }
   if (right - left > count) {
      area = right - left;
   }
   if (right === left) {  // "right === left なら right++"
      right++;
   } else {  // "そうでなければ sum - A[left]" 
      sum -= A[left];
   }
   left++;  // "left を 1 進める"
}
console.log(count);

hogeちゃんの画像

よく解らなかったので C++ と Python3 の解答コード例を参照しました。

問題【STEP: 2】区間の長さ 2

Task

10 個の数列において総和が 15 以下の区間の最大の長さを求めてね。

【区間の長さ 2】コード

reader.on('close', () => {
   const A = lines[0].split(' ').map(Number);
   let [left, right] = [0, 0];
   let sum = 0;
   let count = 0;
   while (left < 10 - count) {
      while (right < 10 && sum + A[right] <= 15) {
         sum += A[right];
         right++;
      }
      if (right - left > count) {
         count = right - left;
      }
      if (right === left) {
         right++;
      } else {
         sum -= A[left];
      }
      left++;
   }
   console.log(count);
});

hogeちゃんの画像

配列 A の値を標準入力から受け取っている以外は【STEP: 1】と同じです。

問題【STEP: 3】区間の長さ 3

Task

10 個の数列において総和が K 以下の区間の最大の長さを求めてね。

【区間の長さ 3】コード

reader.on('close', () => {
   const K = lines[0];
   const A = lines[1].split(' ').map(Number);
   let [left, right] = [0, 0];
   let sum = 0;
   let count = 0;
   while (left < 10 - count) {
      while (right < 10 && sum + A[right] <= K) {
         sum += A[right];
         right++;
      }
      if (right - left > count) {
         count = right - left;
      }
      if (right === left) {
         right++;
      } else {
         sum -= A[left];
      }
      left++;
   }
   console.log(count);
});

hogeちゃんの画像

求める区間が 15以下から K 以下になりましたがそれ以外は【STEP: 2】と同じです。

問題【FINAL】区間の長さ 4

Task

N 個の数列において総和が K 以下の区間の最大の長さを求めてね。

【区間の長さ 4】コード

reader.on('close', () => {
   const [N, K] = lines[0].split(' ').map(Number);
   const A = lines[1].split(' ').map(Number);
   let [left, right] = [0, 0];
   let sum = 0;
   let count = 0;
   while (left < N - count) {
      while (right < N && sum + A[right] <= K) {
         sum += A[right];
         right++;
      }
      if (right - left > count) {
         count = right - left;
      }
      if (right === left) {
         right++;
      } else {
         sum -= A[left];
      }
      left++;
   }
   console.log(count);
});

hogeちゃんの画像

与えられる整数が 10個から N 個になりましたがそれ以外は【STEP: 3】と同じです。

コメント