paiza 問題集平方分割 js

クエリメニュー【累積和・区間和・二次元累積和・二次元区間和・平方分割のバケット・平方分割】

Task

数列 A ・K 個の整数 Q_1〜Q_K が与えられるので A_1〜A_{Q_i} の和を求めてね。

【STEP: 1】コード

reader.on('close', () => {
  const [N, K] = lines[0].split(' ').map(Number);
  const A = [];  // 入力値
  const S = [0];  // A の累積和
  for (let i = 0; i < N; i++) {
    A.push(Number(lines[i + 1]));  // A に 入力値を保存
    S.push(S[i] + A[i]);  // S に A の累積和を保存
  }
  for (let i = N + 1; i <= N + K; i++) {
    const Q = Number(lines[i]);
    console.log(S[Q]);  // S[Q] (A[0]〜A[Q-1]の総和) を出力
  }
});

S は配列 A の累積和を保存するための配列です。S[i + 1] の値は S[i] + A[i] になりました。

top

問題【STEP: 2】区間和

Task

数列 A・K 個の区間 (l, r) が与えられるので A の区間和 A_{l} + 〜+ A_{r} を求めてね。

【STEP: 2】コード

reader.on('close', () => {
  const [N, K] = lines[0].split(' ').map(Number);
  const A = [];
  const S = [0];  // A の累積和
  for (let i = 0; i < N; i++) {
    A.push(Number(lines[i + 1])); // A に 入力値を保存
    S.push(S[i] + A[i]);  // S に A の累積和を保存
  }
  for (let i = N + 1; i <= N + K; i++) {
    const [l, r] = lines[i].split(' ').map(Number);
    console.log(S[r] - S[l - 1]);  // A[r - 1] 〜 A[l -1] の総和
   }
});

【STEP: 1】と同じく S は配列 A の累積和を保存するための配列です。例えば A[3] から A[5] までの各値の和は S[6]-S[3]でした。

top

問題【STEP: 3】二次元累積和

Task

二次元配列 A と累積和を求めたい範囲の情報が与えられるので累積和を求めてね。

【STEP: 3】コード

reader.on('close', () => {
   const [H, W, N] = lines[0].split(' ').map(Number);
   const A = [];  // H ☓ W の2次元配列
   const S = [new Array(W + 1).fill(0)];  // A の2次元累積和 (H + 1) ☓ (W + 1)
   for (let i = 1; i <= H; i++) {
      A.push(lines[i].split(' ').map(Number));  // A に 入力値(配列)を保存
      S.push([0]);  // S に [0] を追加
   }
   for (let h = 0; h < H; h++) {
      for (let w = 0; w < W; w++) {
         S[h + 1][w + 1] = S[h][w + 1] + S[h + 1][w] - S[h][w] + A[h][w];
　　　　// 二次元累積和 = 左の値 + 上の値 - 左斜め上の値 + A[h][w]
      }
   }
   for (let i = H + 1; i <= N + H; i++) {
      const [y, x] = lines[i].split(' ').map(Number);
      console.log(S[y][x]);  // y ✕ x (矩形領域)の2次元累積和
   }
});

S はニ次元配列 A の累積和を保存するための二次元配列です。 S[h + 1][w + 1] の値は S[h][w + 1] + S[h + 1][w] - S[h][w] + A[h][w]で求めています。

top

問題【STEP: 4】二次元区間和

Task

二次元配列の区間和を出力してね。

【STEP: 4】コード

reader.on('close', () => {
   const [H, W, N] = lines[0].split(' ').map(Number);
   const A = [];
   const S = [new Array(W + 1).fill(0)];
   for (let i = 1; i <= H; i++) {
      A.push(lines[i].split(' ').map(Number));
      S.push([0]);
   }
   for (let h = 0; h < H; h++) {
      for (let w = 0; w < W; w++) {
         S[h + 1][w + 1] = S[h][w + 1] + S[h + 1][w] - S[h][w] + A[h][w];
      }
   }
   for (let i = H + 1; i <= N + H; i++) {
      const [sy, sx, ey, ex] = lines[i].split(' ').map(Number);
      console.log(S[ey][ex] - S[sy - 1][ex] - S[ey][sx - 1] + S[sy - 1][sx - 1]);
// 矩形領域の累積和 = 右下(領域内) - 左下の左隣(領域外) - 右上の上(領域外) + 左上の斜め上(領域外)
   }
});

【STEP: 3】と同様に 2次元累積和 S を生成し領域内の右下 – 左下の左隣 – 右上の真上 +左上の斜め上で区間和を求めることができました。console.table(S)で S の値をテーブル形式で出力すると解りやすいと思います。

top

問題【STEP: 5】平方分割のバケット

Task

配列 A を 100 要素ずつに区切ったときの先頭から i 番目の区間の最大値を出力してね。

【STEP: 5】コード

reader.on('close', () => {
   const N = 10000;
   const R = Math.sqrt(N);  // N の平方根
   const A = [];
   for (let i = 0; i < N; i++) {
      A.push(Number(lines[i]));  // 入力値を A に保存
   }
   for (let i = 0; i < R; i++) {
      const a = A.splice(0, R);  // A の値を先頭から R 個切り取り…
      A.push(a);  // 切り取った値(配列)を A の末尾へ挿入
   }
   A.forEach(a => {
      console.log(Math.max(...a));
   });
});

Math.sqrt(N) で N ( A の要素数) の平方根 (100)を求め Aの値を100ずつ切り取った値の最大値 Math.max(...a) を求めて出力しました。

top

問題【FINAL】平方分割

Task

配列 A の区間 A[l_i] … A[r_i] の最大の要素の値を出力してね。

【FINAL】コード

reader.on('close', () => {
   const N = 10000;
   const R = Math.sqrt(N);  // N の平方根
   const K = Number(lines[0]);  // 区間の個数
   const A = [];
   const M = [];
   for (let i = 1; i <= N; i++) {
      A.push(Number(lines[i]));  // 入力値を A に保存
   }
   for (let i = 0; i < R; i++) {
      const a = A.splice(0, R);  // A の値を先頭から R 個切り取り…
      A.push(...a);  // 切り取った値(配列)を A の末尾へ挿入
      M.push(Math.max(...a));
   }
   for (let n = N + 1; n <= N + K; n++) {
      const [l, r] = lines[n].split(' ').map(x => x - 1);
    //console.log(Math.max(...A.slice(l, r + 1)));
      let ans = A[l];
      let i = l;
      while (i <= r) {
         if (i % R === 0 && i + R - 1 <= r) {  // i mod R = 0 且つ i + 99 が 範囲内に収まれば
            ans = Math.max(ans, M[i / R]);  // ans (最大値)を ans と M[i / R]の大きい方で更新
            i += R;  // i を i + R (100) で更新
          } else {  // i mod R != 0 なら…
            ans = Math.max(ans, A[i]);  // ans (最大値)を ans と A[i]の大きい方で更新
            i++;
         }
      }
      console.log(ans);
   }
});

【STEP: 5】と同様に配列 M を生成。A の添字が R で割り切れて I + 99 が終点以下の場合は ans と M[i / R] を比較し大きい方で ans を上書き。それ以外は ans と A[i] を比較し同様に ans を上書き

余談ですが。。

A[l]〜A[r]までの要素を切り取って最大値を求めてもOKでした。

//console.log(Math.max(...A.slice(l, r + 1)));

top