累積和 メニュー【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));
問題文の解説 を参照しながら実装しました。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));
累積和をとる前の配列(入口に +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));
});
長方形領域の 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));
});
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));
});
長方形領域の 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));
});
与えられる 長方形領域 の 個数 が 標準入力 から与えられました。それ以外は【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));
});
マス目の領域が 5 ☓ 5 から N ☓ N になりました。それ以外は【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));
});
マス目の領域が N ☓ N から N ☓ M になりました。それ以外は【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));
});
2次元配列を2つ生成したパターン…。
コメント