ドーナツ (2次元累積和・区間和)

Posted at 2025-08-04

今回は paiza のクエリで「ドーナツ」の問題に挑戦！

問題概要

◆ 問題設定

この店では, チョコが埋め込まれた四角のドーナツが名物となっている
H × W のグリッド状の生地があり、各マスにはチョコの個数（0以上の整数）が書かれている。
この生地の上に、複数の「ドーナツ型の型抜き」を使って、何個のチョコが含まれているかを数えたい。

◆ ドーナツ型の定義

ドーナツは「外側がB×Bの正方形」「内側がS×Sの正方形の穴」からなる。
つまり、「大きな正方形から小さな正方形をくり抜いた形」がドーナツ。
B, S は奇数で、常に B > S が保証されている。
ドーナツの中心座標 (y, x) が与えられ、そこを中心に正方形が配置される。
くり抜いた内側の正方形は常に外側に完全に収まる（境界外に出ない）ことが保証されている。

◆ 入力

最初の1行に、以下が与えられる：

H W N

H：グリッドの行数（高さ）
W：グリッドの列数（幅）
N：ドーナツのクエリ数

続くH行に、グリッド上の各マスに含まれるチョコ数が与えられる（0以上の整数）。

続くN行に、各ドーナツ型の情報が与えられる：

y x B S

y, x：ドーナツの中心座標（1-based index）
B：外側正方形の一辺の長さ（奇数）
S：内側（くり抜かれる部分）の一辺の長さ（奇数）

◆ 出力

各ドーナツごとに、ドーナツ型部分に含まれるチョコの合計数を1行ずつ出力する。

◆ 条件

B, S は奇数で、くり抜けない形状は与えられない

入力例:

出力例:

✅ OK例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];

rl.on('line', (input) => lines.push(input));

rl.on('close', () => {
    const [H, W, N] = lines[0].split(' ').map(Number); // 高さH, 幅W, クエリ数N
    const gridChoco = lines.slice(1, H + 1).map(line => line.split(' ').map(Number)); // チョコの数が書かれたグリッド
    const queries = lines.slice(H + 1); // ドーナツのクエリ情報

    // 累積和テーブルを初期化（H+1 × W+1 の0埋め配列）
    const prefixSum = Array.from({ length: H + 1 }, () => Array(W + 1).fill(0));

    // 二次元累積和を構築（1-based indexで処理）
    for (let y = 1; y <= H; y++) {
        for (let x = 1; x <= W; x++) {
            prefixSum[y][x] = gridChoco[y - 1][x - 1]
                            + prefixSum[y - 1][x]
                            + prefixSum[y][x - 1]
                            - prefixSum[y - 1][x - 1];
        }
    }

    // クエリ処理（各ドーナツに対して）
    for (const q of queries) {
        const [y, x, B, S] = q.split(' ').map(Number); // 中心座標(y, x)、外側サイズB、くり抜きサイズS

        const b = Math.floor(B / 2); // 外側の半径
        const s = Math.floor(S / 2); // 内側の半径（くり抜く部分）

        // 外側の正方形範囲のチョコ数
        const outer = getSum(y - b, x - b, y + b, x + b);

        // 内側の正方形範囲のチョコ数（くり抜かれる部分）
        const inner = getSum(y - s, x - s, y + s, x + s);

        // ドーナツ部分のチョコ数 = 外側 - 内側
        const result = outer - inner;
        console.log(result);
    }

    /**
     * 指定された矩形 (topY, leftX) 〜 (bottomY, rightX) のチョコ数を返す
     * 1-based index を前提としているので注意
     */
    function getSum(topY, leftX, bottomY, rightX) {
        const result = prefixSum[bottomY][rightX]
                     - prefixSum[topY - 1][rightX]
                     - prefixSum[bottomY][leftX - 1]
                     + prefixSum[topY - 1][leftX - 1];

        return result;
    }
});

🗒️ 解説・まとめ

① 2次元累積和を構築

目的：任意の正方形領域内のチョコ数を高速で求めるため。
計算量：
- 前処理：O(H × W)
- クエリ処理：O(1)（getSum関数を1回呼ぶだけ）

② 外側と内側の正方形の区間和を取得

外側正方形（B×B）：ドーナツの全体。
内側正方形（S×S）：ドーナツのくり抜かれた部分（穴）。
方法：
- 中心から半径（(B-1)/2, (S-1)/2(=半径)）を使って上下左右の範囲を決定。
- 範囲の区間和を、2次元累積和で1回の式で高速に取得。

③ ドーナツ部分のチョコ数 = 外側 − 内側

面積の差＝ドーナツとして残る部分。
累積和を使っていれば、各矩形の区間和は1回の計算（定数時間）で求まるため、高速に複数のクエリに対応できる。

僕の失敗談(´;ω;｀)と解決法🐈

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up