1 次元上のいもす法《累積和》

累積和メニュー【1 次元上のいもす法 1 〜 4】

問題【STEP: 1】1 次元上のいもす法1
Task
10 個の マスの 5 つの 各範囲に含まれるマスに 1 加算した値の最大値は？
いもす法を用いて求めてね。

【1 次元上のいもす法 1】コード

const A = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
  // 区間の入口と出口のみに加算と減算(いもす法)
  // 1 〜 3 マス目
A[0]++;  // 区間の入口 + 1
A[3]--;  // 区間の出口 - 1
  // 1 〜 8 マス目
A[0]++;  // 区間の入口 + 1
A[8]--;  // 区間の出口 - 1
  // 3 〜 8 マス目
A[2]++;  // 区間の入口 + 1
A[8]--;  // 区間の出口 - 1
  // 3 〜 6 マス目
A[2]++;  // 区間の入口 + 1
A[6]--;  // 区間の出口 - 1
  // 7 〜 9 マス目
A[6]++;  // 区間の入口 + 1
A[9]--;  // 区間の出口 - 1
  // A = [ 2, 0, 2, -1, 0, 0, 0, 0, -2, -1]
const S = [0];  // 累積和
for (let i = 0; i < 10; i++) {
   S.push(S[i] + A[i]);
}
  // S = [0, 2, 2, 4, 3, 3, 3, 3, 3, 1, 0]
console.log(Math.max(...S));  // S を展開して 最大値を出力
hogeちゃんの画像

配列 A に対し 問題文の指示通り 加算・減算を行い 配列 S に A の累積和を保存。出力時に展開して 最大値を出力しました。ところで… いもす法の “いもす” の語源って何?

top
問題【STEP: 2】1 次元上のいもす法 2
Task
10 個の マスの 5 つの 各範囲に含まれるマスに 1 加算した値の最大値は？
いもす法を用いて求めてね。

【1 次元上のいもす法 2】コード

reader.on('close', () => {
   const A = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
   const S = [0];
   for (let i = 0; i < 5; i++) {
      [L, R] = lines[i].split(' ').map(Number);  // L 〜 R マスの区間の…
      A[L - 1]++;  // 入口 + 1
      A[R]--;  // 出口 - 1
   }
   for (let i = 0; i < 10; i++) {
      S.push(S[i] + A[i]);  // S[i + 1]は A[i]までの累積和
   }
   console.log(Math.max(...S));  // S を展開して 最大値を出力
});
hogeちゃんの画像

区間の範囲 の 入り口は L・出口は R 。それ以外は【STEP: 1】と同じでした。

top
問題【STEP: 3】1 次元上のいもす法 3
Task
10 個の マスの 5 つの 各範囲に含まれるマスに 1 加算した値の最大値は？
いもす法を用いて求めてね。

【1 次元上のいもす法 3】コード

reader.on('close', () => {
   const N = Number(lines[0]);
   const A = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
   const S = [0];
   for (let i = 1; i <= N; i++) {
      [L, R] = lines[i].split(' ').map(Number);
      A[L - 1]++;
      A[R]--;
   }
   for (let i = 0; i < 10; i++) {
      S.push(S[i] + A[i]);  // S[i + 1]は A[i]までの累積和
   }
   console.log(Math.max(...S));  // S を展開して 最大値を出力
});
hogeちゃんの画像

区間の範囲 の 数が N 個になりました。それ以外は【STEP: 2】と同じ。

top
問題【FINAL】1 次元上のいもす法 4
Task
10 個の マスの 5 つの 各範囲に含まれるマスに 1 加算した値値の最大値は？
いもす法を用いて求めてね。

【1 次元上のいもす法 4】コード

reader.on('close', () => {
   const [N, Q] = lines[0].split(' ').map(Number);
   const A = new Array(N).fill(0);
   const S = [0];
   for (let i = 1; i <= Q; i++) {
      const [L, R] = lines[i].split(' ').map(Number);
      A[L - 1]++;
      A[R]--;
   }
   for (let i = 0; i < N; i++) {
      S.push(S[i] + A[i]);
   }
   console.log(Math.max(...S));
});
hogeちゃんの画像

A の 要素数が N 個・区間の範囲 の 数が Q 個になりました。それ以外は【STEP: 3】と同じ。

top

コメント