累積和の練習問題《累積和 応用編》

【復習問題 その 1】コード

reader.on('close', () => {
   const [N, A, B] = lines[0].split(' ').map(Number);
   const a = lines[1].split(' ').map(Number);
   const S = [0];  // a の累積和を保存する配列
   for (let i = 0; i < N; i++) {
      const sum = S[i] + a[i];  // sum は a[0] 〜 a[i] の総和
      S.push(sum);  // S に sum を保存
   }
   console.log(S[B + 1] - S[A]);  // a[0] 〜 a[B]の総和 - a[0] 〜 a[A] の総和
});

入力例1 ( a = [1, 2, 3, 4, 5] ) の場合

s (a の累積和) = [0, 1, 3, 7, 10, 15]

になります。※ s[i+1] = s[i] + a[i]

【復習問題 その 2】コード

reader.on('close', () => {
   const [N, K] = lines[0].split(' ').map(Number);
   const a = lines[1].split(' ').map(Number);
   const S = [0];  // a の累積和を保存する配列
   for (let i = 0; i < N; i++) {
      const sum = S[i] + a[i];  // sum は a[0] 〜 a[i] の総和
      S.push(sum);  // S に sum を保存
   }
   let max_sum = 0;  // 連続する K 個の整数の総和の最大値
   for (let i = 0; i <= N - K; i++) {
      const sum = S[i + K] - S[i];  // 連続する K 個の整数の総和
      if (sum > max_sum) {  // sum が max_sumより大きければ
         max_sum = sum;  // max_sum を sum で上書き
      }
   }
   console.log(max_sum);
});

累積和を使えば 連続する K 個の整数の総和は s[i + K] – s[i] で求めることができました。

【復習問題 その 3】コード

reader.on('close', () => {
   const data = lines[0].split(' ');
   const C = data.pop();
   const [N, X, Y] = data.map(Number);
   const str = lines[1].split('');  // 入力を一文字ずつの配列に変換
   for (let i = 0; i < N; i++) {
      if (str[i] === C) {  // str[i] が C なら
         str[i] = 1;  // str[i] を 1 で上書き
      } else {  // C 以外なら
         str[i] = 0;  // ０ で上書き
      }
   }
   const S = [0];  // str の 累積和
   for (let i = 0; i < N; i++) {
      S.push(S[i] + str[i]);
   }
   console.log(S[Y] - S[X - 1]);
});

C の個数を求めるために str[i]がC なら str[i] を 1 で上書き。それ以外の文字なら ０で上書きしています。

【練習問題 その 1】コード

  // 元の数字 + a_0 → 元の数字 + ( a_0 + a_1 ) → 元の数字 + ( a_0 + a_1 + a_2)
reader.on('close', () => {
   const N = Number(lines[0]);
   const a = lines[1].split(' ').map(Number);
   const S = [0];  // a の累積和
   const bord = [0];  // 黒板に書かれた数字の履歴
   for (let i = 0; i < N; i++) {
      S.push(S[i] + a[i]);  // a[0]〜a[i] の総和
   }
   S.shift();
   for (let i = 0; i < N; i++) {
      const num = bord[i] + S[i];  // (元の数字) + (a[0]〜a[i - 1]の総和)
      bord.push(num);
   }
   console.log(Math.max(...bord));
});

累積和に累積和を加算…。

【練習問題 その 2】コード

reader.on('close', () => {
   const [N, A, B] = lines[0].split(' ').map(Number);
   const str = lines[1].split('');
   const a = new Array(N - 2).fill(0);
  // str[i]から始まる 3文字が 'piz' と一致すれば a[i]= 1 一致しなければ a[i]= 0
   const S = [0];  // a の累積和
   for (let i = 0; i < N - 2; i++) {
      const sub = str[i] + str[i + 1] + str[i + 2];  // str[i]〜 str[i + 2] の連結文字
      if (sub === 'piz') {  // sub が 'piz' と一致すれば
         a[i] = 1;  // a[i] は 1
      }
      S.push(S[i] + a[i]);  // 同時進行で S に S[i] + a[i] を追加
   }
   console.log(S[B - 2] - S[A - 1]);
});

str の 部分文字列 の 一文字目(str[i])を 基準に 続く2文字と連結した文字列が″piz″と一致すれば a[i] = 1; として″piz″の出現数を累積和しました。

【練習問題 その 3】コード

reader.on('close', () => {
   const N = Number(lines[0]);
   const a = lines[1].split(' ').map(Number);
   const S = [0];
   const abs = new Set();  // Set() に sum1 - sum2 の 絶対値 を保存
   for (let i = 0; i < N; i++) {
      S.push(S[i] + a[i]);
   }
   for (let K = 1; K <= N; K++) {  
      const sum1 = S[K];  // a[0] 〜 a[K] の 総和
      const sum2 = S[N] - S[K];  // a[K + 1]〜a[N - 1] の 総和
      const num = Math.abs(sum1 - sum2);  // sum1 - sum2 の 絶対値
      abs.add(num);
   }
   console.log(Math.min(...abs));
});

abs = []; にしても OK なんでけど 実行速度は abs = new Set(); にした方が早くなるみたいね。

【練習問題 その 4】コード

reader.on('close', () => {
   const a = new Array(1000).fill(0);  // 要素数 1000 個の配列(初期値は全て 0)
   const S = [0,...a];  // 要素数 1001 個の配列(初期値は全て 0)
   for (let i = 1; i <= 1000; i++) {
      if (i % 3 === 0 && i % 5 === 0) {  // i が3 と 5 の両方で割り切れれば…
         a[i - 1] = 1;  // a[i - 1] を 1 で上書き
      }
      S[i] = S[i - 1] + a[i - 1];  // S[i] を S[i - 1] + a[i - 1] で上書き
   }
   const Q = Number(lines[0]);
   for (let i = 1; i <= Q; i++) {
      const [L, R] = lines[i].split(' ').map(Number);
      console.log(S[R] - S[L - 1]);  // (a[0] 〜 a[R - 1] の総和) - (a[0] - a[L - 2] の総和)
   }
});

累積和って 色々使えて便利…。

【練習問題 その 5】コード 1/2

reader.on('close', () => {
   const N = Number(lines[0]);
   const a = lines[1].split(' ').map(Number);
   const max1 = [0, a[0]];
   const max2 = [a[N - 1]];
   for (let K = 1; K <= N - 2; K ++) {  // K = 1 の場合から K = N - 2
      max1.push(Math.max(max1[K], a [K]));
      max2.push(Math.max(max2[K - 1], a[N - K - 1]));  // a [K +1] 〜 a [N -1] の最大値を max2 
   }
   max2.reverse();
   for (let K = 1; K <= N - 2; K ++) {  // K = 1 の場合から K = N -2
      console.log(Math.min(max1[K], max2[K]));  // (max1[K], max2[K]) の小さい方
   }
});

累積和の組み込み方が ( ‥)? でしたが とりあえず こんな感じで…。因みに コード2は累積和は組み込んでいませんが、出力値は同じでした。

【練習問題 その 5】コード 2/2

reader.on('close', () => {
   const N = Number(lines [0]);
   const a = lines [1].split(' ').map(Number);
   const s1 = [];
   const s2 = [];
   const max1 = [];
   const max2 = [];
   for (let i = 0; i < N; i ++) {
      s1 .push(a [i ]);
      s2 .push(a [N - i - 1]);
      max1 [i] = Math.max(...s1 );
      max2 [i] = Math.max(...s2 );
   }
   for (let K = 1; K <= N - 2; K ++) {
      console.log(Math.min(max1 [K - 1], max2 [N - K - 2]));
   }
});

累積和ナシのパターンでした。