蟻本初級編攻略 - 2-1 迷路の最短路
ここらへんは全部今年の三月に記事を書いているなー。
このころは
map_をdict化すればかなり綺麗になるが、競プロ的にどうなんだろう・・・
などと言っていたが、現在は躊躇なくdictionary化するなあ。実際そこのO(N)が問題になることはまずない。（すくなくともABCのD問題くらいでは）
「もしコストが気になるならはじめからdictionaryとしてパースしてしまえばいいじゃない」と心の中のIQ145の女子高生に囁かれて試してみたのが以下のコード：
from collections import deque n, m = map(int, input().split()) maze = {(i,j):c for i in range(n) for j, c in enumerate(input())} def bfs(coord): dq = deque() dq.appendleft((0, coord)) while dq: steps, (i, j) = dq.pop() current = maze.get((i, j), '#') if current == 'G': return steps if current == '#': continue maze[(i, j)] = '#' dirs = ((-1, 0), (1, 0), (0, 1), (0, -1)) dq.extendleft((steps+1, (i+di, j+dj)) for di, dj in dirs) start = next(coord for coord, c in maze.items() if c == 'S') print(bfs(start))
DFSをスタックでやることの隠れたメリットはBFSとDFSがほぼ同型になること。DFSではLIFOのスタックを使っていたのをBFSではFIFOのキューを使う、以外はほぼ同じコード。
ABC007C - 幅優先探索
蟻本の問題とほぼ同じ。スタートとゴールが地図とは別に座標で与えられることとその座標が0-indexedじゃないことが注意点。
from collections import deque n, m = map(int, input().split()) start = tuple(int(x)-1 for x in input().split()) goal = tuple(int(x)-1 for x in input().split()) maze = {(i,j):c for i in range(n) for j, c in enumerate(input())} def bfs(coord): dq = deque() dq.appendleft((0, coord)) while dq: steps, (i, j) = dq.pop() if (i, j) == goal: return steps if maze.get((i, j), '#') == '#': continue maze[(i, j)] = '#' dirs = ((-1, 0), (1, 0), (0, 1), (0, -1)) dq.extendleft((steps+1, (i+di, j+dj)) for di, dj in dirs) print(bfs(start))
AtCoderはほぼすべての問題が1-indexedで修正するのをうっかりすると後から見つけにくい。
ABC088D - Grid Repainting
「BFSの結果のルート」と「元からあった黒いマス」以外のマスをすべて黒く塗れるという点に気づけば、あとはほぼ同じ問題。
from collections import deque h, w = map(int, input().split()) maze = {(i,j):c for i in range(h) for j, c in enumerate(input())} blacks = sum(c == '#' for c in maze.values()) def bfs(i, j): dq = deque() dq.appendleft((1, (i, j))) while dq: steps, (i, j) = dq.pop() if (i, j) == (h-1, w-1): return steps if maze.get((i, j), '#') == '#': continue maze[(i, j)] = '#' dirs = ((-1, 0), (1, 0), (0, 1), (0, -1)) dq.extendleft((steps+1, (i+di, j+dj)) for di, dj in dirs) res = bfs(0, 0) print(-1 if res is None else h*w - res - blacks)
ただ、この問題ではそもそもスタート地点からゴールまでの経路が存在しないケースがあり得る。最初に提出したときはうっかりしていた・・・
ARC005C - 器物損壊！高橋君
壁を二回まで破壊して通過できるという条件でスタートからゴールまで到達できるか、という問題。
最初は「DFSで隣接している壁を探して、隣接している壁がダブっているかどうかで繋がっている『部屋』を見つけて2ステップでゴールまで到達できるか」的なコードを書いていたのだが、あえなくTLEした。
その後に記事の説明を読んで01-BFSなる用語を調べたところ、非常にエレガントな解法で感動した。
「距離」を「移動コスト」再定義して「通路の移動コストは０」「壁の移動コストは１」とすれば「壁を最大二回移動してゴールに到達できるか」が算出できる。
h, w = map(int, input().split()) maze = {(i,j):c for i in range(h) for j, c in enumerate(input())} dirs = ((-1, 0), (1, 0), (0, 1), (0, -1)) def bfs01(start, maze=maze, dirs=dirs): q = [[start], [], []] while q: i, j = q[0].pop() maze[i, j] = 'X' for di, dj in dirs: next_ = maze.get((i+di, j+dj), 'X') if next_ == 'g': return True if next_ == 'X' or (next_ == '#' and len(q) == 1): continue q[next_ == '#'].append((i+di, j+dj)) while q and not q[0]: q = q[1:] return False start = next(coord for coord, c in maze.items() if c == 's') print('YES' if bfs01(start) else 'NO')
ただ、アイディアのエレガンスの対してコード実装が泥臭いのが難点・・・
最初はPriority QueueでやってみたのだがやはりO(n log n)だとTLEになる。リストを束ねて「スタックのキュー」的なデータ構造にした。
これで実行時間は800ms弱。Pythonだとここらへんが上限だろうか？
ちなみにPyPy3で同じコードを走らせてみると、Python3で20msぐらいかかるテストケースで165msかかり、すこし重いテストケースは軒並みMLEを起こしていた。
すくなくともAtCoderでPyPy3は使い物にならないと言ってしまってもいいのではないか。
理由としては：
- JITコンパイラが温まりきらない（数秒は継続して走っていないとJITの恩恵を受けない）
- PyPyはCPythonよりスタートアップに時間がかかる
- PyPy3はPyPy2に比べて最適化などがまだ甘い（Python2.7の仕様がもう10年もほとんど変わっていないので追いやすかった？）
- AtCoderが使っているPyPy3のバージョンが「CPython3より遅いことも多い」と知られている古いバージョン
- PyPyはitertoolsやlist comprehensionなどよりfor loopなどのほうが効率化しやすい
などが挙げられると思う。これらを合わせると正直PyPy3は当面無視するのが得策だろう。AtCoderでCythonが使えたらなかなか面白いことになるとは思うが・・・
