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

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

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

const A = []; // 6行 6列の2次元配列
for (let i = 0; i < 6; i++) {
   A[i] = [];
   for (let j = 0; j < 6; j++) {
      A[i][j] = 0; // 初期値は全て 0
   }
}
// console.table(A);
const points = [
   [1, 1, 3, 3],
   [2, 2, 4, 4],
   [3, 3, 5, 5],
   [1, 3, 3, 5],
   [3, 1, 5, 3],
];
for (let i = 0; i < 5; i++) {
   const [sx, sy, ex, ey] = points[i];
   A[sy - 1][sx - 1]++;   // 入口に +1
   A[sy - 1][ex]--;   // 出口に -1
   A[ey][sx - 1]--;   // 入口に +1 出口に -1
   A[ey][ex]++;   // 重複に +1
}
// console.table(A);
for (let i = 0; i <= 5; i++) {
   for (let j = 0; j < 5; j++) {
      A[i][j + 1] += A[i][j];  // 横方向の累積和
   }
}
// console.table(A);
for (let i = 0; i <= 5; i++) {
   for (let j = 0; j < 5; j++) {
      //   console.log(A[j][i]);
      A[j + 1][i] += A[j][i];  // 縦方向の累積和
   }
}
// console.table(A);
const MAX = [];  // 各行の最高値を保存するための配列
for (let i = 0; i < 5; i++) {
   MAX.push(Math.max(...A[i]));
}
console.log(Math.max(...MAX));
hogeちゃんの画像

問題文の解説 を参照しながら実装しました。2次元配列の出力は console.table() を使えば わかりやすいですね。

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

const A = [];  // 累積和をとる前(2次元配列)
const S = [];  // 2次元累積和
for (let i = 0; i < 6; i++) {  // 6 行
   A.push([]);  // 2次元配列
   S.push([]);  // 2次元配列
   for (let j = 0; j < 6; j++) {  // 6 列
      A[i].push(0);  // 初期値は全て 0
      S[i].push(0);  // 初期値は全て 0
   }
}
const points = [
   [1, 1, 3, 3],
   [2, 2, 4, 4],
   [3, 3, 5, 5],
   [1, 3, 3, 5],
   [3, 1, 5, 3]
];
for (let i = 0; i < 5; i++) {  // 5 つの範囲に対して…
   const [sx, sy, ex, ey] = points[i].map(e => e - 1);
   A[sy][sx]++;  // 左上(範囲内)に + 1
   A[sy][ex + 1]--;  // 右上(範囲外)に + 1
   A[ey + 1][sx]--;  // 左下(範囲外)に + 1
   A[ey + 1][ex + 1]++;  // 右下(範囲外)に + 1
}
for (let i = 1; i <= 5; i++) {
   for (let j = 1; j <= 5; j++) {
      S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i-1][j-1];
      // 2次元累積和 = 直上の値 + 直左の値 - 直左斜め上の値 + 累積和をとる前の値
   }
}
  // console.table(A);
  // console.table(S);
const Sf = S.flat();
console.log(Math.max(...Sf));
hogeちゃんの画像

累積和をとる前の配列(入口に +1, 出口右に-1, 出口左に-1, 重複に+1)と累積和を保存する配列を別個に生成しました。こっちの方が 直感的に理解しやすいかも…。

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

reader.on('close', () => {
   const A = []; // 6行 6列の2次元配列
   for (let i = 0; i < 6; i++) {
      A[i] = [];
      for (let j = 0; j < 6; j++) {
         A[i][j] = 0;  // 初期値は全て 0
      }
   }
// console.table(A);
   for (let i = 0; i < 5; i++) {
      const [a, b] = lines[i].split(' ').map(Number);
      const [sx, sy, ex, ey] = [a, 3, b, 3];
      A[sy - 1][sx - 1]++;   // 入口に +1
      A[sy - 1][ex]--;   // 出口に -1
      A[ey][sx - 1]--;   // 出口に -1
      A[ey][ex]++;   // 重複に +1
   }
// console.table(A);
   for (let i = 0; i <= 5; i++) {
      for (let j = 0; j < 5; j++) {
         A[i][j + 1] += A[i][j];  // 横方向の累積和
      }
   }
// console.table(A);
   for (let i = 0; i <= 5; i++) {
      for (let j = 0; j < 5; j++) {
         // console.log(A[j][i]);
         A[j + 1][i] += A[j][i];  // 縦方向の累積和
      }
   }
// console.table(A);
   const MAX = [];  // 各行の最高値を保存するための配列
   for (let i = 0; i < 5; i++) {
      MAX.push(Math.max(...A[i]));
   }
   console.log(Math.max(...MAX));
});
hogeちゃんの画像

長方形領域の x 座標 が 標準入力から与えられました。それ以外は【STEP: 1】と同じです。

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

reader.on('close', () => {
   const A = [];  // 累積和をとる前(2次元配列)
   const S = [];  // 2次元累積和
   for (let i = 0; i < 6; i++) {  // 6 行
      A.push([]);  // 2次元配列
      S.push([]);  // 2次元配列
      for (let j = 0; j < 6; j++) {  // 6 列
         A[i].push(0);  // 初期値は全て 0
         S[i].push(0);  // 初期値は全て 0
      }
   }
   for (let i = 0; i < 5; i++) {  // 5 つの範囲に対して…
      const [y, x] = lines[i].split(' ').map(e => e - 1);
      const [sx, sy, ex, ey] = [y, 3, x, 3];
      A[sy][sx]++;  // 左上(範囲内)に + 1
      A[sy][ex + 1]--;  // 右上(範囲外)から - 1
      A[ey + 1][sx]--;  // 左下(範囲外)から - 1
      A[ey + 1][ex + 1]++;  // 右下(範囲外)に + 1
   }
   for (let i = 1; i <= 5; i++) {
      for (let j = 1; j <= 5; j++) {
         S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i-1][j-1];
        // 2次元累積和 = 直上の値 + 直左の値 - 直左斜め上の値 + 累積和をとる前の値
      }
   }
  // console.table(A);
  // console.table(S);
   const Sf = S.flat();
   console.log(Math.max(...Sf));
});
hogeちゃんの画像

2次元配列を2つ生成したパターンでした。

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

reader.on('close', () => {
   const A = []; // 6行 6列の2次元配列
   for (let i = 0; i < 6; i++) {
      A[i] = [];
      for (let j = 0; j < 6; j++) {
         A[i][j] = 0;  // 初期値は全て 0
      }
   }
// console.table(A);
   for (let i = 0; i <= 5; i++) {
      const [sx, sy, ex, ey] = lines[i].split(' ').map(Number);
      A[sy - 1][sx - 1]++;   // 入口に +1
      A[sy - 1][ex]--;   // 出口に -1
      A[ey][sx - 1]--;   // 出口に -1
      A[ey][ex]++;   // 重複に +1
   }
// console.table(A);
   for (let i = 0; i <= 5; i++) {
      for (let j = 0; j < 5; j++) {
         A[i][j + 1] += A[i][j];  // 横方向の累積和
      }
   }
// console.table(A);
   for (let i = 0; i <= 5; i++) {
      for (let j = 0; j < 5; j++) {
         //   console.log(A[j][i]);
         A[j + 1][i] += A[j][i];  // 縦方向の累積和
      }
   }
// console.table(A);
   const MAX = [];  // 各行の最高値を保存するための配列
   for (let i = 0; i < 5; i++) {
      MAX.push(Math.max(...A[i]));
   }
   console.log(Math.max(...MAX));
});
hogeちゃんの画像

長方形領域の x 座標 と y 座標 が 標準入力から与えられました。それ以外は【STEP: 2】と同じです。

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

reader.on('close', () => {
   const N = Number(lines[0]);
   const A = []; // 6行 6列の2次元配列
   for (let i = 0; i <= 5; i++) {
      A[i] = [];
      for (let j = 0; j <= 5; j++) {
         A[i][j] = 0;  // 初期値は全て 0
      }
   }
// console.table(A);
   for (let i = 1; i <= N; i++) {
      const [sx, sy, ex, ey] = lines[i].split(' ').map(Number);
      A[sy - 1][sx - 1]++;   // 入口に +1
      A[sy - 1][ex]--;   // 出口に -1
      A[ey][sx - 1]--;   // 出口に -1
      A[ey][ex]++;   // 重複に +1
   }
// console.table(A);
   for (let i = 0; i <= 5; i++) {
      for (let j = 0; j < 5; j++) {
         A[i][j + 1] += A[i][j];  // 横方向の累積和
      }
   }
// console.table(A);
   for (let i = 0; i <= 5; i++) {
      for (let j = 0; j < 5; j++) {
         //   console.log(A[j][i]);
         A[j + 1][i] += A[j][i];  // 縦方向の累積和
      }
   }
// console.table(A);
   const MAX = [];  // 各行の最高値を保存するための配列
   for (let i = 0; i < 5; i++) {
      MAX.push(Math.max(...A[i]));
   }
   console.log(Math.max(...MAX));
});
hogeちゃんの画像
与えられる 長方形領域 の 個数 が 標準入力 から与えられました。それ以外は【STEP: 3】と同じです。

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

reader.on('close', () => {
   const [N, K] = lines[0].split(' ').map(Number);
   const A = [];
   for (let i = 0; i <= N; i++) {
      A.push([0]);
      for (let j = 0; j <= N; j++) {
         A[i][j] = 0;
      }
   }
   for (let i = 1; i <= K; i++) {
   for (let i = 1; i <= N; i++) {
      const [sx, sy, ex, ey] = lines[i].split(' ').map(Number);
      A[sy - 1][sx - 1]++;   // 入口に +1
      A[sy - 1][ex]--;   // 出口に -1
      A[ey][sx - 1]--;   // 出口に -1
      A[ey][ex]++;   // 重複に +1
   }
// console.table(A);
   for (let i = 0; i <= N; i++) {
      for (let j = 0; j < N; j++) {
         A[i][j + 1] += A[i][j];  // 横方向の累積和
      }
   }
// console.table(A);
   for (let i = 0; i <= N; i++) {
      for (let j = 0; j < N; j++) {
         //   console.log(A[j][i]);
         A[j + 1][i] += A[j][i];  // 縦方向の累積和
      }
   }
// console.table(A);
   const MAX = [];  // 各行の最高値を保存するための配列
   for (let i = 0; i < N; i++) {
      MAX.push(Math.max(...A[i]));
   }
   console.log(Math.max(...MAX));
});
hogeちゃんの画像

マス目の領域が 5 ☓ 5 から NN になりました。それ以外は【STEP:4 】と同じです。

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

reader.on('close', () => {
   const [N, M, K] = lines[0].split(' ').map(Number);
   const A = [];
   for (let i = 0; i <= N; i++) {
      A.push([0]);
      for (let j = 0; j <= M; j++) {
         A[i][j] = 0;
      }
   }
   for (let i = 1; i <= K; i++) {
      const [sx, sy, ex, ey] = lines[i].split(' ').map(Number);
      A[sy - 1][sx - 1]++;   // 入口に +1
      A[sy - 1][ex]--;   // 出口に -1
      A[ey][sx - 1]--;   // 出口に -1
      A[ey][ex]++;   // 重複に +1
   }
// console.table(A);
   for (let i = 0; i <= N; i++) {
      for (let j = 0; j < M; j++) {
         A[i][j + 1] += A[i][j];  // 横方向の累積和
      }
   }
// console.table(A);
   for (let i = 0; i <= M; i++) {
      for (let j = 0; j < N; j++) {
         //   console.log(A[j][i]);
         A[j + 1][i] += A[j][i];  // 縦方向の累積和
      }
   }
// console.table(A);
   const MAX = [];  // 各行の最高値を保存するための配列
   for (let i = 0; i < N; i++) {
      MAX.push(Math.max(...A[i]));
   }
   console.log(Math.max(...MAX));
});
hogeちゃんの画像

マス目の領域が NN から NM になりました。それ以外は【STEP:5】と同じです。

【STEP: 2】コード

reader.on('close', () => {
   const [N, M, K] = lines.splice(0, 1)[0].split(' ').map(Number);
   const A = [];  // 累積和をとる前(2次元配列)
   const S = [];  // 2次元累積和
   for (let i = 0; i <= N; i++) {  // N + 1行
      A.push([]);  // 2次元配列
      S.push([]);  // 2次元配列
      for (let j = 0; j <= M; j++) {  // M + 1列
         A[i].push(0);  // 初期値は全て 0
         S[i].push(0);  // 初期値は全て 0
      }
   }
   for (let i = 0; i < K; i++) {  // K 個の範囲に対して…
      const [sx, sy, ex, ey] = lines[i].split(' ').map(e => e - 1);
      A[sy][sx]++;  // 左上(範囲内)に + 1
      A[sy][ex + 1]--;  // 右上(範囲外)から - 1
      A[ey + 1][sx]--;  // 左下(範囲外)から - 1
      A[ey + 1][ex + 1]++;  // 右下(範囲外)に + 1
   }
   for (let i = 1; i <= N; i++) {
      for (let j = 1; j <= M; j++) {
         S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i-1][j-1];
        // 2次元累積和 = 直上の値 + 直左の値 - 直左斜め上の値 + 累積和をとる前の値
      }
   }
  // console.table(A);
  // console.table(S);
   const Sf = S.flat();
   console.log(Math.max(...Sf));
});
hogeちゃんの画像

2次元配列を2つ生成したパターン…。

 

コメント