今回は paiza の「平方分割のバケット」問題に挑戦！
問題概要
paiza くんは、数列の特定区間の最大値を効率よく求めたいと考えている。
もし毎回その区間を全て調べる方法を使うと、最大で O(NK) の時間がかかってしまい、クエリ数が多い場合に非常に非効率である。
そこで「平方分割」というアルゴリズム・手法を使い、あらかじめ区間ごとの情報をまとめておくことで、処理を高速化したい。
↓ 平方分割
- 長さ N の配列が与えられたとき、N の平方根 x を求め、配列を長さ x の配列に分割し、それぞれの配列について目的の値を調べておく。
（分割で得られる最後の配列の長さは必ずしも x になるとは限りません）- 調べたい区間に完全に含まれている配列についての 1. で求めた値と、その配列以外の部分の値を全て調べて、目的の値を求める。
この問題では、長さ 10,000 の数列 A について手順 1. を行う。
10,000 の平方根は 100 なので、先頭から 100 要素ずつの最大値を求めて出力せよ。
入力される値
A_1
...
A_10000
期待する出力
ans_1
...
ans_100
✅ OK例：
const rl = require('readline').createInterface( { input:process.stdin });
const arrA = [];
rl.on('line', (input) => arrA.push(Number(input)));
rl.on('close', () => {
const result = [];
for(let i = 1; i <= 100; i++){
const temp = arrA.slice((i - 1) * 100, i * 100);
result.push(Math.max(...temp));
}
console.log(result.join('\n'));
});
-
slice((i – 1) * 100, i * 100)：
例）i=1 のとき →slice(0, 100)→ A₁〜A₁₀₀
-
Math.max(…temp)：配列の最大値を展開して求める
-
result.join(‘\n’)：1行ずつ出力形式に整形
🔍 改めて何をやっているか
長さ 10,000 の配列 arrA を、
→ 100 要素ずつ（√10000 = 100）に区切って
→ 各区間ごとに 最大値 を求めている。
🔎 補足：平方分割って本来どう使う？
この問題は準備（前処理）だけだけど、実際には以下の手順で使う。
- √N 個の「ブロック」に分ける
- 各ブロックにあらかじめ最大値などを保存
- クエリ（範囲の最大など）が来たら：
- ブロックをまたいでいないなら：そのまま調べる
- ブロックをまたいでいるなら：
- 両端は1個ずつ調べる
- 真ん中は 前処理した最大値を参照 → 高速！
🔧 問題設定（例）
長さ N = 12 の配列 A があるとする：
A = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8]
ここに対して、次のような「区間最大値クエリ」が複数回くるとする：
Q1. A[2..7] の最大値は？ ← 回答：9
Q2. A[5..12] の最大値は？ ← 回答：9
Q3. A[1..4] の最大値は？ ← 回答：4
🔍 普通にやると？
各クエリで 全部調べると O(N) × クエリ数（K）
function maxNaive(l, r) {
let max = -Infinity;
for (let i = l; i <= r; i++) {
max = Math.max(max, A[i]);
}
return max;
}
→ クエリが多いと遅い！
✅ 平方分割で高速化
🔹① 前処理：√Nごとにブロックを分ける
12の平方根 ≒ 3.46 → 切り上げて 4 にする
配列Aを4つのブロックに分ける：
ブロック0: A[0..2] = [3, 1, 4] → 最大4
ブロック1: A[3..5] = [1, 5, 9] → 最大9
ブロック2: A[6..8] = [2, 6, 5] → 最大6
ブロック3: A[9..11] = [3, 5, 8] → 最大8
→ blockMax = [4, 9, 6, 8]
🔹② クエリ回答の流れ（例：Q2: A[5..12]）
端の余り部分（5~5）と（9~12）は手動で調べる
完全に含まれるブロック（6~8）は blockMax[2] を使う！
A[5] = 9 ← 自分で調べる
block 2 = 6 ← blockMax[2]
A[9..11] = 3,5,8 ← 自分で調べる
--------------------------
→ max(9, 6, 8) = 9
これでループが最大 √N 回で済む！
🟩 コードスケッチ（簡易）
const A = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
const n = A.length;
const blockSize = Math.ceil(Math.sqrt(n));
const blockMax = new Array(blockSize).fill(-Infinity);
// 前処理：ブロック最大値を計算
for (let i = 0; i < n; i++) {
const b = Math.floor(i / blockSize);
blockMax[b] = Math.max(blockMax[b], A[i]);
}
// クエリ処理関数
function query(l, r) { // 0-indexed
let maxVal = -Infinity;
while (l <= r && l % blockSize !== 0) maxVal = Math.max(maxVal, A[l++]); // 前半余り
while (l + blockSize - 1 <= r) {
maxVal = Math.max(maxVal, blockMax[Math.floor(l / blockSize)]);
l += blockSize;
}
while (l <= r) maxVal = Math.max(maxVal, A[l++]); // 後半余り
return maxVal;
}
📌 まとめ：平方分割とは
| 特徴 | 内容 |
|---|---|
| 目的 | 範囲クエリ（最大/最小/合計など）の高速化 |
| 前処理時間 | O(N) |
| 1回のクエリ時間 | O(√N) |
| 対応できる操作 | 加算・最大・最小など（可換な操作） |