Xmas Contest 2019 C: Sokoban 解説
https://atcoder.jp/contests/xmascon19/tasks/xmascon19_c
問題概要
倉庫番の盤面が与えられるので (入力公開)，解くのに必要な最小手数を求めよ．
sample, 01, 02
小さいので，手で遊んで解けます．しかし，解くだけなら簡単ですが最小手数は非自明だったりします．コンテストでは，見つかった解から 手ずつ減らして提出してみるのもありだと思います．
確実なプログラミング解ももちろん可能で，盤面の状態数を考えてみると，たとえば 02 ではうさぎの位置は 通り，そのそれぞれに対し箱の位置が
通り，と抑えられて，特に枝刈り等せずとも BFS で最小手数を求めることができます．
01 は，解くだけなら本当に簡単なのを適当に作ってみました． 手の解がとても見えやすいと思いますが，うまいことやると減って不思議です．
02 は，左上の空間を利用できる問題を作ってみました (パズルとしての問題ならよくありそう)．左上に何度も行くのをやめるのが大事でそれをすると 手の解が見えやすいと思うのですが，やっぱりうまいことやると減って，よくわかりません……．ちなみに最後に片づく荷物が左上か右下しかありえないので，奇数手であることがわかって提出を少し節約できたりします．
03
荷物が壁の直角の隅に置かれてしまうと，そこがゴールでない限り詰んでしまいます．このことから，入力にたくさん現れる
########### ####....### ...#.##.... ##.@..##### ###...##### ###########
という部分が一方通行の役割を果たすことがわかります (上の図の向きでは左から右へのみ，一定の手数で，荷物の位置を変えずに通れます)．入力の右下の荷物を片付けに行けばよいので， の部屋のようなものを頂点とした最短路問題として解くことができます．
04
列ごとに
########### ########... ##...##.@.. #.@..##.#.# ..#.###.#.. #.#.@.@..## #..#...#.## ##.#.....## #.@####.#.. #....##..@. #..#...##.. ###..#.##@. ##.@##..... ##....###.. ##..#.##### #####.##### ........... ###########
というパターンが繰り返される構造になっています．左から右へ抜けたいのですが，そのためには右下を回って箱を一度ずらす必要があり，そうすると一旦下から出て一番左まで戻らないといけません．よって，右から 番目のブロックを左から右へ抜けるためには
回来なければならない，そのそれぞれに対して右から
番目のブロックを左から右へ抜けるために
回ずつ，
回来なければならない，そのそれぞれに対して……，というようにして，右から
番目のブロックに
回来なければなりません．これに，各ブロックでかかる手数 (手で遊んで数えるのがよいと思います) を掛けて足すことで答えが求まります．
この入力は，盤のサイズに対して指数手数かかる例になっています．手でクリアしようとすると絶望を感じられると思います．
05
03 で使われていた一方通行のパターンが荷物が片付いていない状態で登場しています．左上の部分は最後に訪れないといけないので，グラフの問題で言い換えると「すべての辺を少なくとも 回通ってスタート位置に戻ってくるための最小コスト」を求める問題になっています．
これは，(有向) 中国人郵便配達問題として知られた問題です．辺を通る回数分増やして考えると，すべての辺をちょうど 回ずつ通ってスタート位置に戻って来られる条件は (グラフが強連結かつ) すべての頂点の出次数と入次数が等しいことです (Euler circuit)．ということで，最初のグラフに辺を足して出次数と入次数を等しくする問題と言い換えられますが，その最小コストは入次数が余っている点から出次数が余っている辺へ流す最小費用流問題を解くことで求めることができます．
omake
html にのみ入っているこのデータ，パズルガチ勢であるところのすぬけさんが作りました．最短手数の証明が怪しくて出題を見送ったのですが，参加者の方によってすごく縮められていて，こわいです．わたしは，解けません．
統計情報
得点 01 02 03 04 05 人数 100 o o o o o 1 60 o o o o 7 43 o o o 8 35 o o o 6 18 o o 39 11 o 5 7 o 53
正解者：DEGwer さん (2:39:03)
コメント
倉庫番の盤面が与えられたとき解の有無を判定する問題は PSPACE 完全であることが知られています．倉庫番のパーツを作って Turing machine をエミュレートするという証明です．この論文の見どころは，平面交差です．
そんなわけで実質任意の決定可能問題は倉庫番で表せるのですが，自然なのはグラフの問題で，その中でコンテストであまり頻繁には見かけない (気がする) 郵便配達が思いついたので出してみたくてこのような形になったのでした．
