区間内の個数《累積和》

累積和メニュー【区間内の個数 1 〜 4】

問題【STEP: 1】区間内の個数 1
Task
数列の a[2]から a[7]までの偶数の個数を 累積和を使うことで求めてね。

【区間内の個数 1】コード

const a = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4];
const b = new Array(10);  // 10 = a の要素数
const s = [0];  // b の 累積和
for (let i = 0; i < 10; i++) {
   a[i] % 2 === 0 ? b[i] = 1 : b[i] = 0;  // a[i]が偶数→b[i] = 1,奇数→b[i] = 0
   s.push(s[i] + b[i]);  // s[i + 1] = s[i] + b[i] 
}
  // b = [0, 0, 0, 0, 0, 0, 1, 0, 1, 1]
  // s = [0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3]
console.log(s[8] - s[2]);  // 範囲の右端 - 左端の直左 を出力
hogeちゃんの画像

a[i] が 偶数 なら b[i] は1 。奇数なら b[i] は０。s に b の累積和を保存。s[8] から s[2] を減算すれば 答えが得られました。詳しくは 問題文の(ヒント) をご参照下さい。

top
問題【STEP: 2】区間内の個数 2
Task
a[2]から a[7]までの偶数の個数を 累積和を使うことで求めてね。

【区間内の個数 2】コード

reader.on('close', () => {
   const a = lines[0].split(' ').map(Number);
   const b = new Array(10);  // 10 = a の要素数
   const s = [0];  // b の 累積和
   for (let i = 0; i < 10; i++) {
      a[i] % 2 === 0 ? b[i] = 1 : b[i] = 0;  // a[i]が偶数→b[i] = 1,奇数→b[i] = 0
      s.push(s[i] + b[i]);  // s[i + 1] = s[i] + b[i] 
   }
   console.log(s[8] - s[2]);  // 範囲の右端 - 左端の直左 を出力
});
hogeちゃんの画像

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

top
問題【STEP: 3】区間内の個数 3
Task
数列の a_X から a_Y までの偶数の個数を 累積和を使うことで求めてね。

【区間内の個数 3】コード

reader.on('close', () => {
   const [X, Y] = lines[0].split(' ').map(Number);
   const a = lines[1].split(' ').map(Number);
   const b = new Array(10);  // 10 = a の要素数
   const s = [0];  // b の 累積和
   for (let i = 0; i < 10; i++) {
      a[i] % 2 === 0 ? b[i] = 1 : b[i] = 0;  // a[i]が偶数→b[i] = 1,奇数→b[i] = 0
      s.push(s[i] + b[i]);  // s[i + 1] = s[i] + b[i] 
   }
   console.log(s[Y + 1] - s[X]);  // 範囲の右端 - 左端の直左 を出力
});
hogeちゃんの画像

含まれる偶数の数を調べる区間が a[X] 〜 a[Y] に指定されました。それ以外は【STEP: 2】と同じです。

top
問題【FINAL】区間内の個数 4
Task
数列の a_X から a_Y までの偶数の個数を 累積和を使うことで求めてね。

【区間内の個数 4】コード

reader.on('close', () => {
  const [N, X, Y] = lines[0].split(' ').map(Number);
  const a = lines[1].split(' ').map(Number);
  const b = new Array(N);  // N = a の要素数
  const s = [0];  // b の 累積和
  for (let i = 0; i < N; i++) {
    a[i] % 2 === 0 ? b[i] = 1 : b[i] = 0;  // a[i]が偶数→b[i] = 1,奇数→b[i] = 0
    s.push(s[i] + b[i]);  // s[i + 1] = s[i] + b[i] 
  }
  console.log(s[Y + 1] - s[X]);  // 範囲の右端 - 左端の直左 を出力
});
hogeちゃんの画像

配列 a の要素数が N 個になりましたが それ以外は【STEP: 3】と同じです。

top

コメント