はじめに
先日のAtcoderBeginnerContest293で、Mo's Algorithmを使う問題が出題されました。
私は結局この問題が解けずに終わり、後からMoについて勉強したので、その考え方をまとめておきます。
ぞうきんがけ問題
競プロの問題ではないですが、以下のような問題を考えてみます。
$N \times N$マスからなる正方形の部屋がある。
1つのマスからは上下左右4方向に隣接するマスへと移動できるが、部屋の外へ出ることはできない。
全てのマスは汚れていて、あなたはぞうきんで汚れを拭き取らなければならない。
全てのマスを掃除し終わるのに必要な移動回数の最小値を求めよ。
なお掃除の開始地点は一番左下のマスとする。
例えば、$N=9$だとこんな感じのグリッドマップになります。
同じマスを複数回掃除するのは無駄なので、各マスへ訪れる回数はそれぞれ1回ずつで十分です。ぞうきんがけの移動ルートは①②のようなものが考えられます。
全てのマスに移動しなければならないので、どう頑張っても移動回数は$O(N^2)$になってしまいますが、移動ルートは他にも色々と考えられます。例えば以下の③のように、幅3のまとまりごとに分けて掃除してもよいです。これなんかは現実世界でぞうきんがけをやる時の動きに近いですね。
改めて考えてみると、①②③はそれぞれ幅1,9,3でのぞうきんがけをやっていると解釈できます。
では、$N \times N$マスのうち、汚れているのが以下に赤色で示した$Q(=13)$マスだけならどうなるでしょうか。
汚れていないマスに移動する必要はないので、先ほど考えたルート①②③から、無駄な移動を省くことができます。
なんとなく、③の移動回数が少なそうに見えますね。このように、汚れが$Q$マスしかない場合に、最適なぞうきんがけ幅がどのくらいになるのか考えてみます。
ぞうきんがけ幅の最適化
ぞうきんがけ幅を$D$で表し、左端から右端への移動まとまりを「ブロック」と呼ぶことにします。
左右方向と上下方向に分けて、トータルの移動回数を見積もってみましょう。
左右方向の移動回数
各ブロックの内側では、左右移動は一方通行なので、移動回数は$O(N)$です。
ブロックの個数が$O(\frac{N}{D})$なので、左右方向の移動回数は全部で$O(\frac{N^2}{D})$回になります。
上下方向の移動回数
無駄な移動はしたくないので、上下の移動理由は基本的に汚れマスに到達するための位置調整です。
$Q$個ある汚れマスごとに$O(D)$の上下位置調整が必要なので、
上下方向の移動回数は全部で$O(QD)$回になります。
厳密にはブロックとブロックの間をまたぐ時にも上下移動しますが、全体からすると無視できます1。
トータルの移動回数
結局、左右と上下をあわせたトータルの移動回数は$O(\frac{N^2}{D} + QD)$です。
このときは$D=\frac{N}{\sqrt{Q}}$とするのが適切で2、トータル移動回数を$O(N \sqrt{Q})$まで減らすことができます。
それで結局、何が嬉しいのか
以下のような問題を考えてみます。
長さ$N$の配列が与えられる。
続いて$Q$個のクエリが与えられるので、それらを処理せよ。
なお$i(1 \leq i \leq Q)$番目のクエリは区間$[L_i, R_i]$として与えられるので、
その配列区間に対応するほにゃららの値を出力せよ。
ぞうきんがけの話を適用することで、この問題に$O(N \sqrt{Q})$で答えられるようになります。
なぜかというと、区間$[L_i, R_i]$というのは、
$N \times N$マスの正方形部屋における2次元座標$(L_i, R_i)$とみなせるからです。
適当な初期値$[L, R]$に対応する値を求めたら、
その値を$O(N \sqrt{Q})$回くらい微修正すればよいのです。
$N \sim 10^5, Q \sim 10^5$ であれば2sec制限でも間に合いそうです！
以上がMo's Algorithmの基本的な考え方です3。
マジ天才的だと思います。ただし、実際に競プロでMoを使うためには、問題が満たしていなければならない条件がもう2つあります。
適用条件
ひとつめは、汚れマスが勝手に増減したり移動したりしないことです。
せっかく立てた効率的な移動プランが狂ってしまい、無駄な移動コストがかかってしまいます。
競プロ的な表現で言うと、すべての固定区間$[L,R]$について、対応する値が
各クエリを処理する過程で変わらないこと＝配列の値が変わらないことが必要です。
要はクエリの中に配列書き換え命令が含まれているとダメで、クエリを先読みできる必要があります。
ふたつめは、マスからマスへの移動コストが$O(1)$であることです。
競プロ的な表現で言うと、ある区間$[L, R]$に対応する値がわかっているときに
その$L$や$R$を$\pm 1$した別区間に対応する値が$O(1)$で計算できることが必要です。
ぞうきんがけ問題では隣接マス間の移動コストが$O(1)$であることを前提にしていましたが、
区間に対応する値の計算がいつも高速に行えることは限りません。
サンプルコード
Rustでライブラリ化したものです。処理すべき区間クエリをinto_iterで順番に取り出せるようにしています。
mod mo {
use std::vec::IntoIter;
// 区間クエリ情報を格納していく構造体
pub struct Mo {
ls: Vec<usize>, // 各区間クエリの左端
rs: Vec<usize>, // 各区間クエリの右端
}
// 区間クエリ情報を適切な順番で取り出すIterator構造体
pub struct MoIterator {
index_iter: IntoIter<usize>,
ls: Vec<usize>,
rs: Vec<usize>,
}
impl Mo {
// 初期化
pub fn new() -> Self {
Self {
ls: vec![],
rs: vec![],
}
}
// クエリ追加
pub fn add_range_query(&mut self, l: usize, r: usize) {
self.ls.push(l);
self.rs.push(r);
}
// Iteratorへの変換。すべてのクエリ登録が終わった後にコールされる想定
pub fn into_iter(self) -> MoIterator {
let n = self.rs.iter().max().unwrap(); // クエリ処理につかう配列区間のサイズ
let q = self.rs.len(); // クエリの総数
let d = n / ((q as f64).sqrt() as usize + 1) + 1; // 最適なブロック幅の算出。ゼロ割防止のため一応+1しておく
// 処理順番の最適化
let mut indexes = (0..q).collect::<Vec<_>>();
indexes.sort_by_cached_key(|&i| {
// ブロック単位で縦方向にソートしつつ、各ブロックの中身は横方向にソート。
// 偶数行ブロックと奇数行ブロックで移動方向を逆にする。
let block_index = self.ls[i] / d;
if block_index % 2 == 0 {
(block_index, self.rs[i])
} else {
(block_index, n - self.rs[i])
}
});
MoIterator {
index_iter: indexes.into_iter(),
ls: self.ls,
rs: self.rs,
}
}
}
// Iterator挙動の実装
impl Iterator for MoIterator {
type Item = (usize, (usize, usize));
fn next(&mut self) -> Option<Self::Item> {
if let Some(i) = self.index_iter.next() {
Some((i, (self.ls[i], self.rs[i]))) // 処理順≠入力順なので、入力順indexもセットで返す
} else {
None
}
}
}
}
最後に
もし理解が進んだ方は、ぜひMo's Algorithmを使って解ける問題に挑戦してみて下さい。
ABC174F Range Set Query
ABC293G Triple Index