今回は paiza の「九九表の色塗り」の問題に挑戦！
問題概要
与えられているもの
- 巨大な九九表
- 縦：10^18 マス
- 横：10^18 マス
- マス
(i,j)にはi×jの数字 が書かれている - 小さなパターン
- サイズ：縦
H× 横W（最大 500×500） -
#：黒マス -
.：白マス
- サイズ：縦
パターンの敷き詰め方
- 九九表の左上から順に
- 隙間なく、同じパターンを無限に敷き詰める
求めるもの
- 左上が (
h_l,w_l) - 右下が (
h_h,w_h)
この長方形の中にある黒マス（#）だけを対象に、書かれている数値の合計を 1000000007 で割った余りを求める。
ポイント
- 長方形の大きさは最大で10^36
- 1マスずつ見る方法は 絶対に不可能
入力例:
3 3 2 1 5 5
#.#
##.
..#
出力例:
125
✅OK例：
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
// 入力をすべて lines に貯める
const lines = [];
rl.on('line', line => {
lines.push(line.trim());
});
rl.on('close', () => {
let idx = 0;
/* =====================
入力の読み込み
===================== */
let [H, W, hl, wl, hh, wh] = lines[idx++].split(' ').map(BigInt);
// 座標を 0-indexed に直す
hl -= 1n;
wl -= 1n;
hh -= 1n;
wh -= 1n;
// ループ用なので Number にしてOK
H = Number(H);
W = Number(W);
const MOD = 1000000007n;
const modinv2 = (MOD + 1n) / 2n; // 2 の逆元
// パターンの読み込み
const MAP = [];
for (let i = 0; i < H; i++) {
MAP.push(lines[idx++]);
}
/* =====================
BigInt 用 floor 除算
===================== */
function floordiv(a, b) {
// b > 0 を仮定
if (a >= 0n) return a / b;
return -((-a + b - 1n) / b);
}
/* =====================
パターンの (i, j) が
担当するマスの総和を計算
===================== */
function solveProblem(i, j) {
const bi = BigInt(i);
const bj = BigInt(j);
const bH = BigInt(H);
const bW = BigInt(W);
/*
パターン [s, t] の (i, j) は
実座標：
行 = s * H + i
列 = t * W + j
これが指定長方形に入る s, t の範囲を求める
*/
const HL = floordiv(hl - 1n - bi, bH) + 1n;
const HH = floordiv(hh - bi, bH);
const WL = floordiv(wl - 1n - bj, bW) + 1n;
const WH = floordiv(wh - bj, bW);
// そもそも存在しない場合
if (HL > HH || WL > WH) return 0n;
const hCount = HH - HL + 1n;
const wCount = WH - WL + 1n;
/*
行方向の値：
(s*H + i + 1)
→ 初項 HL*H + i + 1
→ 末項 HH*H + i + 1
→ 公差 H
等差数列の和を使う
*/
const H_SUM =
(((HL + HH) * bH + 2n * bi + 2n) % MOD) *
(hCount % MOD) %
MOD *
modinv2 %
MOD;
/*
列方向も同様
*/
const W_SUM =
(((WL + WH) * bW + 2n * bj + 2n) % MOD) *
(wCount % MOD) %
MOD *
modinv2 %
MOD;
// 行と列は独立なので掛け算
return (H_SUM * W_SUM) % MOD;
}
/* =====================
全ての黒マスを合算
===================== */
let ans = 0n;
for (let i = 0; i < H; i++) {
for (let j = 0; j < W; j++) {
if (MAP[i][j] === '#') {
ans = (ans + solveProblem(i, j)) % MOD;
}
}
}
console.log(ans.toString());
});
🔍コードの流れ
① 入力を受け取る
-
H, W：パターンの高さ・幅 -
hl, wl, hh, wh：求めたい長方形の範囲 -
MAP：#/.のパターン
② 座標を 0-indexed に直す
- 問題文は 1-indexed
- 計算しやすくするため全部
-1して 0-indexed に変換
③ 「巨大な九九表」を直接見ない方針を取る
- 縦横 10^18 はループ不可
-
H×Wごとに同じパターンが繰り返されることを利用
④ 各パターンマス (i, j) を独立に考える
-
(i, j)が#のときだけ処理 - このマスが、無限に敷き詰められたどの位置に現れるかを考える
⑤ (i, j) が現れる実座標の式
- 行：
s * H + i - 列：
t * W + j -
s,tは「何枚目のパターンか」
⑥ 長方形に入る s と t の範囲を求める
hl ≤ s*H + i ≤ hhwl ≤ t*W + j ≤ wh- これを解いて
-
HL ～ HH（縦方向） -
WL ～ WH（横方向）
を求める
-
-
BigIntのfloor除算を使うのが重要
⑦ 行方向の数値の合計を計算
- 各マスの値は
(行番号 + 1) - 等差数列になるので公式で一気に合計
⑧ 列方向も同じことをする
-
(列番号 + 1)の等差数列の和を計算
⑨ 行の和 × 列の和 = (i, j) の総寄与
- 九九表なので掛け算
- これが
(i, j)1マス分の合計
⑩ 全ての # マスについて足し合わせる
H × W ≤ 250000- 余裕で回せる
- 最後に
MODを取って出力
📝まとめ
① 全体を直接見るのを諦める
- 10^36 マスは無理
- 「1パターンの1マス」に注目する
② パターンの 1 マス (i, j) に注目
-
(i, j)が#のときだけ考える - このマスは無限に繰り返し現れる
③ 実際の座標を数式で表す
- 行番号：
s * H + i - 列番号：
t * W + j -
s,t：何枚目のパターンか
④ 指定長方形に入る範囲を求める
- 条件：
h_l ≤ s*H + i ≤ h_hw_l ≤ t*W + j ≤ w_h
- これを解くと：
-
s の範囲 →HL ～ HH` -
tの範囲 →WL ～ WH
-
※ BigInt の floor 除算が必須
⑤ 数値の合計は「等差数列」
- 行方向：
-
(s*H + i + 1)が並ぶ
-
- 列方向：
-
(t*W + j + 1)が並ぶ
-
- どちらも等差数列 → 公式で一気に合計
⑥ 九九表なので掛け算
- 値は (行番号 + 1) × (列番号 + 1)
- 行の総和 × 列の総和 →
(i, j)1マス分の寄与
⑦ 全ての # マスを足す
- 最大
H×W= 250,000 - これは余裕でループ可能
-
MODを取りながら合計