PAST5H
H - コンベア
https://gyazo.com/f0e4b1e3e154ed74f38484fa80a6fd5a
初回考察
動かせるか判定
グラフを構築して、各始点から「ゴールにたどり着けるか」をDFS
頂点数10^6、大丈夫？
スタートがたくさん、ゴールは一つ
→ゴールをスタートにする
グラフを逆辺で作っておき、ゴールを始点として到達可能頂点を探索する。
各頂点高々4本の辺しか持たないのでO(N)で間に合う
考察完了
実装
グラフを逆辺で作り、ゴールから再帰呼び出しDFSでたどりつく頂点をマーク
10TLE
コンテスト後に試しにPython3で出してみたら14TLE
グラフを構築しないで地図データを使って探索
コンテスト中は3TLE 1MLEだったとメモされてるが、今出し直してみたら3TLEだった、勘違いかな？
Python3だと1MLE
再帰呼び出しでの探索をwhileループに書き換え
1TLE
結果出力での文字列結合を減らす
文字列をループの中で結合しないでリストにappendしておき、最後にjoinする
AC
考察
今回、問題条件から最悪の場合頂点数が10^6になる
Pythonで頂点ごとにリストを持つ実装の場合、その構築コスト自体が無視できない
到達可能性チェックを再帰呼び出しDFSで実装したが、PyPyの関数呼び出しは遅い
MLEは何が悪いか…
文字列結合を減らしてないのは単純にうっかりミス
念のためグラフ構築しつつ文字列結合だけ減らしてみたのを提出してみたが、これは9TLEだったから主要因ではない
code:python
def solve(H, W, R, C, world):
visited = False * (WIDTH * HEIGHT)
stack = {WIDTH * R + C}
while len(stack) > 0:
pos = stack.pop()
visitedpos = True
next = pos - 1
if not visitednext:
if worldnext == 1 or worldnext == 2:
stack.add(next)
next = pos + 1
if not visitednext:
if worldnext == 1 or worldnext == 3:
stack.add(next)
next = pos + WIDTH
if not visitednext:
if worldnext == 1 or worldnext == 4:
stack.add(next)
next = pos - WIDTH
if not visitednext:
if worldnext == 1 or worldnext == 5:
stack.add(next)
for y in range(ORIGINAL_HEIGHT):
line = []
for x in range(ORIGINAL_WIDTH):
pos = WIDTH + 1 + WIDTH * y + x
if worldpos == 0:
line.append("#")
elif visitedpos:
line.append("o")
else:
line.append("x")
print("".join(line))