区間の数え上げ《しゃくとり法》

累積和メニュー

hogeちゃん

2022.09.13

累積和メニュー【区間の数え上げ 1 〜 4】

問題【STEP: 1】区間の数え上げ 1

Task

10個の数列。長さが 1以上で総和が 15以下の区間はいくつ？しゃくとり法で求めてね。

【区間の数え上げ 1】コード

// しゃくとり法(Two Pointer Approach)
// result = 出力値, sum = 区間の総和, right = 区間の右端, N = 数列の要素数, K = 境界値
const TPA = (result, sum, right, N, K) => {
   for (let left = 0; left < N; left++) {  // 区間の左端
      while (right < N && sum + A[right] <= K) {  // right が N 未満で sum が K 以下の間…
         sum += A[right];  // sum に A[right] を加算
         right++;  // 右端を1つ進める
      }
      result += right - left;  // 右端のindex - 左端のindex
      if (right === left) {  // 右端 と 左端 が同じなら
         right++;  // 右端を1つ進める
      } else {
         sum -= A[left];  // 総和 から 左端の値 を減算
      }
   }
   return result;
};
const A = [1, 5, 9, 1, 20, 5, 3, 6, 5, 4];
console.log(TPA(0, 0, 0, 10, 15));

hogeちゃんの画像

問題文の解説を参照しながら実装しました。

問題【STEP: 2】区間の数え上げ 2

Task

10 個の数列。長さが 1 以上で総和が 15 以下の区間はいくつ？しゃくとり法をで求めてね。

【区間の数え上げ 2】コード

reader.on('close', () => {
// しゃくとり法(Two Pointer Approach)
// result = 出力値, sum = 区間の総和, right = 区間の右端, N = 数列の要素数, K = 境界値
   const TPA = (result, sum, right, N, K) => {
      for (let left = 0; left < N; left++) {  // 区間の左端
         while (right < N && sum + A[right] <= K) {  // right が N 未満で sum が K 以下なら…
            sum += A[right];  // sum に A[right] を加算
            right++;  // 右端を1つ進める
         }
         result += right - left;  // 右端のindex - 左端のindex
         if (right === left) {  // 右端 と 左端 が同じなら
            right++;  // 右端を1つ進める
         } else {
            sum -= A[left];  // 総和 から 左端の値 を減算
         }
      }
      return result;
   };
   const A = lines[0].split(' ').map(Number);
   console.log(TPA(0, 0, 0, 10, 15));
});

hogeちゃんの画像

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

問題【STEP: 3】区間の数え上げ 3

Task

10 個の数列。長さが 1 以上で総和が K 以下の区間はいくつ？しゃくとり法で求めてね。

【区間の数え上げ 3】コード

reader.on('close', () => {
// しゃくとり法(Two Pointer Approach)
// result = 出力値, sum = 区間の総和, right = 区間の右端, N = 数列の要素数, K = 境界値
   const TPA = (result, sum, right, N, K) => {
      for (let left = 0; left < N; left++) {  // 区間の左端のindex
         while (right < N && sum + A[right] <= K) {  // right が N 未満で sum が K 以下なら…
            sum += A[right];  // sum に A[right] を加算
            right++;  // 右端を1つ進める
         }
         result += right - left;  // 右端のindex - 左端のindex
         if (right === left) {  // 右端 と 左端 が同じなら
            right++;  // 右端を1つ進める
         } else {
            sum -= A[left];  // 総和 から 左端の値 を減算
         }
      }
      return result;
   };
   const k = Number(lines[0]);
   const A = lines[1].split(' ').map(Number);
   console.log(TPA(0, 0, 0, 10, k));
});

hogeちゃんの画像

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

問題【FINAL】区間の数え上げ 4

Task

N 個の数列。長さが 1 以上で総和が K 以下の区間はいくつ？しゃくとり法で求めてね。

【区間の数え上げ 4】コード

reader.on('close', () => {
// しゃくとり法(Two Pointer Approach)
// result = 出力値, sum = 区間の総和, right = 区間の右端, N = 数列の要素数, K = 境界値
   const TPA = (result, sum, right, N, K) => {
      for (let left = 0; left < N; left++) {  // 区間の左端のindex
         while (right < N && sum + A[right] <= K) {  // right が N 未満で sum が K 以下なら…
            sum += A[right];  // sum に A[right] を加算
            right++;  // 右端を1つ進める
         }
         result += right - left;  // 右端のindex - 左端のindex
         if (right === left) {  // 右端 と 左端 が同じなら
            right++;  // 右端を1つ進める
         } else {
            sum -= A[left];  // 総和 から 左端の値 を減算
         }
      }
      return result;
   };
   const [n, k] = lines[0].split(' ').map(Number);
   const A = lines[1].split(' ').map(Number);
   console.log(TPA(0, 0, 0, n, k));
});

hogeちゃんの画像

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

コメント