JOI 2022/2023 本選 問題 3
迷路 (Maze) 解説
解説担当 : tatyam

1

問題概要

マスのマス目があり，通れるマスと通れないマスがある．
マスの領域を選び，通れるようにする操作を何回でも行える．
マスとマスを連結にしたい．
操作回数の最小値は？

2

小課題

1. ( 点)，2. ( 点)．
3. ( 点) 答えは 以下である，
4. ( 点)．
5. ( 点)．
6. ( 点)．
7. ( 点)．
8. ( 点)．

．
．

3

小課題 ( 点)

小課題 ( 点)
これは…？

マスの領域を選び，通れるようにする操作を何回でも行える．

4

小課題 ( 点)5小課題 ( 点)考察① 重みつきグラフへの変換

黒いマスを 個通るのに 回操作が必要
同じ黒マスを複数回通る必要はない

6

小課題 ( 点)考察① 重みつきグラフへの変換

黒いマスを 個通るのに 回操作が必要
同じ黒マスを複数回通る必要はない→ 黒マスを通る回数が最小となる S から G への経路を見つける問題
7

小課題 ( 点)考察① 重みつきグラフへの変換

黒いマスに入る辺のコストを白いマスに入る辺のコストをとすると，頂点 S から頂点 G への最短経路問題になる
8

小課題 ( 点)

小課題 の解法

重み付きグラフの最短路問題→ ダイクストラ法でそれでもいいが…？

だ！

9

小課題 ( 点)

小課題 の解法

01 BFS

辺の重みが のみである場合に使える BFS の亜種
BFS では探索する頂点をキュー (queue) に入れていた
01-BFS では探索する頂点を両終端キュー (deque) に入れる10

小課題 ( 点)

BFS の場合探索する頂点を queue に入れる
queue の内部に境界がある．境界の前には始点から距離 の頂点が，境界のの後ろには始点から距離の頂点が入っている11

小課題 ( 点)

BFS の場合探索する頂点を queue に入れる
queue の内部に境界がある
前から頂点を取り出して，隣接する頂点を距離で更新する更新された頂点を queue の後ろに入れる
これらの操作を行なっても は満たされたまま→ 距離の小さい順に探索できる！

12

小課題 ( 点)

01-BFS の場合探索する頂点を deque に入れる
deque の内部に境界がある
前から頂点を取り出して，隣接する頂点を距離 または距離で更新する

13

小課題 ( 点)

01-BFS の場合探索する頂点を deque に入れる
deque の内部に境界がある
前から頂点を取り出して，隣接する頂点を距離 または距離で更新する
距離 で更新された頂点を deque の前に入れる
距離で更新された頂点を dequeの後ろに入れる14

小課題 ( 点)

01-BFS の場合探索する頂点を deque に入れる
deque の内部に境界がある
前から頂点を取り出して，隣接する頂点を距離または距離で更新する
距離 で更新された頂点を deque の前に入れる
距離で更新された頂点を deque の後ろに入れる

これらの操作を行なっても は満たされたまま→ 距離の小さい順に探索できる！

15

小課題 ( 点)

小課題 の解法 まとめ

マス目を辺の重みが または である重み付き有向グラフに変換する
頂点，辺のグラフができる
01-BFS で S から G への最短経路を時間で求める
16

小課題 ( 点)

豆知識 : vector のメモリ再確保
vector<vector<pair<int, int>>>

で頂点の重み付きグラフを作って持つとかなり遅い
vector は 連続したメモリ領域 を使用することが保証されている．確保したメモリ領域が足りなくなった場合は，長さを 倍程度にして メモリを再確保 する．このメモリ再確保はそれなりの時間がかかる．
vector を個作って push_back していくと，メモリ再確保が 回以上起こり，かなり遅くなる．
17

小課題 ( 点)

豆知識 : vector のメモリ再確保

で 頂点の重み付きグラフを作って持つとかなり遅い
vector は 連続したメモリ領域 を使用することが保証されている．確保したメモリ領域が足りなくなった場合は，長さを 倍程度にして メモリを再確保 する．このメモリ再確保はそれなりの時間がかかる．
vector を個作って push_back していくと，メモリ再確保が 回以上起こり，かなり遅くなる．

vector<vector<pair<int, int>>>→ グラフを作らずにその都度 4 方向を調べるようにすると，速いより一般的な方法 : 全部まとめて つの vector に入れる (CSR format)

18

小課題 ( 点)

小課題 ( 点)などの計算量で解けば良い

19

小課題 ( 点)考察② 手で行ける範囲とする．
方向を黒マスで塞がれているとき， 手でどこまで行けるか？

20

小課題 ( 点)21

小課題 ( 点)22

小課題 ( 点)23

小課題 ( 点)24

小課題 ( 点)25

小課題 ( 点)26

小課題 ( 点)27

小課題 ( 点)28

小課題 ( 点)( 手で行ける範囲)(ハンコで塗れる範囲)(そこから白いマスで移動できる範囲)

29

小課題 ( 点)

ハンコで塗れる範囲 はマスの正方形の領域から四隅を取り除いた形

30

小課題 ( 点)考察③ ワープへの言い換え「のハンコを押して移動する」操作は，「ハンコで塗れる範囲 のマスに色を無視してワープする」操作に言い換えることができる．
31

小課題 ( 点)考察③ ワープへの言い換え

ワープする操作は白マスが残らないため，ハンコを押す操作より弱い操作→ (ハンコの場合の最小の操作回数) (ワープの場合の最小の操作回数) は明らか．
(ハンコの場合の最小の操作回数) (ワープの場合の最小の操作回数) を示す．
32

小課題 ( 点)

補題
ハンコを押した後 ハンコで塗れる範囲 を出たら，ハンコで塗れる範囲 には戻ってこないとして良い (最小の操作回数は変わらない)33

小課題 ( 点)

補題
ハンコを押した後 ハンコで塗れる範囲 を出たら，ハンコで塗れる範囲 には戻ってこないとして良い (最小の操作回数は変わらない)
最初から 回目の方へ向かえば良い34

小課題 ( 点)考察③ ワープへの言い換え

ハンコで塗れる範囲 を 回しか出ないのであれば，ハンコをワープで代用できる→ ワープなら 01-BFS で扱える！
35

小課題 ( 点)

小課題 の解法 まとめ

小課題 と同様の 01-BFS
各マスから ハンコで塗れる範囲 へコスト の辺を張る
各マスから隣接する白マスへコスト の辺を張る
辺の数は本なので，01-BFS で36

豆知識 : push 関数を作ろう

小課題 ( 点)

グリッド BFS を書くとき…

while(q.size()) {auto [r, c] = q.front();
q.pop();
if(r > 0 && chmin(cost[r - 1][c], cost[r][c] + 1))
q.emplace(r - 1, c);if(r + 1 < R && chmin(cost[r + 1][c], cost[r][c] + 1))
q.emplace(r + 1, c);if(c > 0 && chmin(cost[r][c - 1], cost[r][c] + 1))
q.emplace(r, c - 1);
if(c + 1 < C && chmin(cost[r][c + 1], cost[r][c] + 1))
q.emplace(r, c + 1);}

同じことを何度も書きすぎ！！

37

小課題 ( 点)
auto push = [&](int r, int c, int x) {if(cost[r][c] <= x) return;
cost[r][c] = x;q.emplace(r, c);};while(q.size()) {auto [r, c] = q.front();
q.pop();
const int x = cost[r][c] + 1;
if(r > 0) push(r - 1, c, x);if(r + 1 < R) push(r + 1, c, x);if(c > 0) push(r, c - 1, x);if(c + 1 < C) push(r, c + 1, x);}

豆知識 : push 関数を作ろう
関数を使ってまとめよう

38小課題 ( 点)
auto push = [&](int r, int c, int x) {if(r < 0 || r >= R || c < 0 || c >= C) return;if(cost[r][c] <= x) return;
cost[r][c] = x;q.emplace(r, c);};while(q.size()) {auto [r, c] = q.front();
q.pop();
const int x = cost[r][c] + 1;
push(r - 1, c, x);push(r + 1, c, x);push(r, c - 1, x);push(r, c + 1, x);}push 関数の中で境界判定をやっても良いですね39

小課題 ( 点)

小課題 ( 点)答えは 以下である．
答えをとして，くらいの計算量で解けば良い

40

小課題 ( 点)考察④ 手で行ける範囲

周囲を黒マスで囲まれているとき，( 手で行ける範囲)(ハンコで塗れる範囲)(そこから白いマスで移動できる範囲)
だった．
41

小課題 ( 点)考察④ 手で行ける範囲
図で整理するとこう42

小課題 ( 点)考察④ 手で行ける範囲

なら，回繰り返せば答えがわかる43

小課題 ( 点)考察④ 手で行ける範囲

なら，回繰り返せば答えがわかる
44

小課題 ( 点)考察④ 手で行ける範囲

そこから白いマスで移動できる範囲 は BFS で求められる．
そこからハンコで塗れる範囲 は全探索だと遅いが，どうやって求める？
45

小課題 ( 点)

そこからハンコで塗れる範囲 を求める

つ前の範囲に入っている各マスから右図の形を伸ばして，それらの和集合を取りた
い．
範囲加算・ 点取得 これは…
いわゆる いもす法！
46

小課題 ( 点)

いもす法

正方形から四隅を抜いた形 をマスの長方形とマスの長方形に分解和集合を取るので，多く加算しても良い47

小課題 ( 点)

いもす法

正方形から四隅を抜いた形 をマスの長方形とマスの長方形に分解和集合を取るので，多く加算しても良いを配置し，後から 次元累積和値が正になった部分が，そこからハンコで塗れる範囲 である．
48

小課題 ( 点)

小課題 の解法
まとめける．

で解49

小課題 ( 点)

豆知識 : queue は空でもByte のメモリを食うや std::stack は別のコンテナ型を用いて動く型である．デフォルトでは std::deque を用いる．
GCC では， std::deque は Byte ごとのブロックでメモリ確保を行う．空でも ブロック確保するため， std::deque は空でも Byte のメモリを食う．
→ queue は std::vector で代用できる．
先頭要素を削除する代わりに 先頭の index を管理 する変数 s を持ち， s++ でpop を行う．
std::queue50

小課題 〜

注意

ここから先は考察要素の組み合わせによって様々な計算量が考えられます．
実装方針による定数倍も様々あり，計算量が同じでも様々な点数になることが予想されます．
実際にグラフを構築して遅くなる
01-BFS の代わりにダイクストラ法を使って をつけるしたがって，考察要素のみを紹介します．
51

小課題 〜

小課題 ( 点)

小課題 ( 点)やに注意すると，などの計算量で解けば良い．などの計算量で解けば良い．
52

小課題 〜

小課題 ( 点)
小課題 ( 点)
小課題 ( 点)やなどの計算量で解けば良い．などの計算量で解けば良い．などの計算量で解けば良い．

53

小課題 〜

考察⑤ 外側しか遷移しなくて良い小課題 では，ハンコで塗れる範囲 を回までしか出ないので，ハンコをワープに言い換えていた．
54

小課題 〜

考察⑤ 外側しか遷移しなくて良い小課題 では，ハンコで塗れる範囲 を回までしか出ないので，ハンコをワープに言い換えていた．
また，各マスから ハンコで塗れる範囲 全てにコスト の辺を張っていた．
55

小課題 〜

考察⑤ 外側しか遷移しなくて良い

Q. ハンコで塗れる範囲 を 回も出ないときってどんなとき？

56

小課題 〜

考察⑤ 外側しか遷移しなくて良い

Q. ハンコで塗れる範囲 を 回も出ないときってどんなとき？
A. ハンコで塗れる範囲 の中にゴールがあるとき

57

小課題 〜

考察⑤ 外側しか遷移しなくて良い
ハンコで塗れる範囲 の中にゴールがあるとき，ゴールにワープできて，終了
ハンコで塗れる範囲 の外にゴールがあるとき，絶対に ハンコで塗れる範
囲 を出なければならない

58

小課題 〜

考察⑤ 外側しか遷移しなくて良いということは，ハンコで塗れる範囲 全部に辺を張る必要はなくて…

59

小課題 〜

考察⑤ 外側しか遷移しなくて良いということは，ハンコで塗れる範囲 全部に辺を張る必要はなくて，最も外側のマスにのみ辺を張れば良い！
※ 範囲内 にゴールがあればゴールへの辺も必要
60

小課題 〜

考察⑤ 外側しか遷移しなくて良い
辺の個数がで，01-BFS で本になったの
時間61

小課題 〜

考察⑥ 解法を組み合わせる

小課題 の計算量はだった．
が大きくなるほど， 度に広い範囲を塗れるので， は小さくなる
具体的には，
62

小課題 〜

考察⑥ 解法を組み合わせるは に反比例して小さくなる
一方，やなどの解法は に比例して時間がかかる→ 解法を組み合わせよう！
63小課題 〜

考察⑥ 解法を組み合わせるが間に合うときは小課題 の解法で，そうでないときは小課題 の解法で解く時間に注意すると，時間であることが分かる
64

小課題 〜

考察⑥ 解法を組み合わせるが間に合うときは外側しか遷移しない解法
で，そうでないときは小課題 の解法
で解く
時間に注意すると，時間であることが分かる
65

小課題 〜区間に辺を張るテクニック

セグメント木状に頂点を増やしておくと，長さの区間に辺を張るのに本必要だったのが，本くらいで張れるようになる
66

小課題 〜区間に辺を張るテクニック
セグメント木状に頂点を用意し，下方向にコスト の辺を張る

67

小課題 〜区間に辺を張るテクニック
セグメント木状に頂点を用意し，下方向にコスト の辺を張る
区間 にコスト の辺を張る

68

小課題 〜区間に辺を張るテクニック
セグメント木状に頂点を用意し，下方向にコスト の辺を張る
区間 にコスト の辺を張る
区間 にコスト の辺を張る

69

小課題 〜区間に辺を張るテクニック
小課題 の時間→時間に外側にしか辺を張らなくていい時間→時間に (定数倍によっては満点を取れる)
注意 : グラフを実際に構築すると遅い
70

小課題 〜

豆知識 : 簡単なセグ
木の作り方
長さ のセグ木にするとよい
出典 : 非再帰セグ木
サイコー！ 一番す
きなセグ木ですp.35

71

小課題 〜区間に辺を張るテクニック②次元セグ木でできるなら， 次元セグ木でもできるよね72

小課題 〜区間に辺を張るテクニック②次元セグ木でできるなら，次元セグ木でもできるよね73

小課題 〜区間に辺を張るテクニック②次元セグ木を使って長方形に辺を張る
小課題 の時間→
時間に (小課題 まで取れる)
注意 : グラフを実際に構築すると遅い
74

小課題 〜区間に辺を張るテクニッ
ク③
列を 個くらいのブロッ
クに区切って，各ブロック内で右側方向に繋げる頂点と，左側方向に繋げる頂点を作る．

75

小課題 〜区間に辺を張るテクニック③

列を 個くらいのブロックに区切って，各ブロック内で右側方向に繋げる頂点と，左側方向に繋げる頂点を作る．
小課題 の時間→時間に外側にしか辺を張らなくていい
時間
→
時間に76

小課題 〜区間に辺を張るテクニッ
ク④
こっちも同様に 次元にできるマスくらいのブロックに区切って，各ブロッ
ク内で右上方向，右下方向，左上方向，左下方向に繋げる頂点を作る

77

小課題 〜区間に辺を張るテクニック④マスくらいのブロックに区切って，各ブロック内で右上方向，右下方向，左上方向，左下方向に繋げる頂点を作る
小課題 の時間→時間に (定数倍が重いので，工夫をしないと小課題 までかも)78

小課題 〜

考察⑦ 段階に分ける

小課題 の解法は，時間の 次元いもす法を回繰り返すのがボトル
ネック
これを全体でにしたい．
79

小課題 〜

考察⑦ 段階に分ける(ハンコで塗れる範囲) (隣接する黒マスを中心にマスの範囲)

80

小課題 〜

考察⑦ 段階に分ける

周囲マスに広げた範囲を計算するには？

81

小課題 〜

考察⑦ 段階に分ける

周囲マスに広げた範囲を計算するには？
→ 縦と横が独立なので，分けてやる
全部 BFS でできるので，時間で解けた！
82

小課題 〜

得点情報

得点 小課題 人数 累積人数83