

以下問題についてです。

atcorder 270 問題3  
<https://atcoder.jp/contests/abc270/tasks/abc270_c>

提出したところ10問のテストが時間切れとなってしまいます。

現在pythonでatcorderに取り組んでいるのはpython力をつけたいという目的もあり、他の言語は使いたくないと考えています。

pythonでかつ再帰処理を使って時間切れとならずに解く方法はありますでしょうか？

[code]

    import sys
    def trace(l,traced,x,y):
        # nodeが持つリンクを全て調査
        flg = 0
        for i in l[x]:
            # 追跡済みじゃなければ値を追加
            if i not in traced:
                traced.append(i)
                flg+=1
                # 目標に到達したら終了
                if i == y:
                    return True
                # 終了以外は追跡を継続
                if not trace(l,traced,i,y):
                    traced.pop()
                    flg -= 1
        # ノードが次の接続先を持っていたかいなか
        return flg
    
    def resolve():
        input = sys.stdin.readline
    
        N,X,Y=map(int, input().split())
    
        l = [[] for _ in range(N+1)]
    
        for _ in [0]*(N-1):
            A,B = map(int,input().split())
            l[A].append(B)
            l[B].append(A)
    
        traced = [X]
        
        trace(l,traced,X,Y)
        
        print(' '.join([str(s) for s in traced]))
    resolve()
    
[/code]


CC BY-SA 4.0
2022-09-25T12:02:07.907
91294
2022-09-25T19:35:42.537
2022-09-25T16:53:03.977
3060
704
question
python アルゴリズム
Python で再帰処理を高速化するには？


コード **6** 行目`if i not in traced:`がボトルネックになっているものと思われます．

参考：  
[Python -
TimeComplexity](https://wiki.python.org/moin/TimeComplexity#:%7E:text=O\(nk\)-,x%20in%20s,O\(n\),-min\(s\)%2C%20max)

* * *

実装は単にDFSを行うだけですが，「このノードはどこのノードから遷移してきたのか」という情報を持つリストを用意し，遷移時にこのリストを更新します．探索終了後，逆順に(yから)辿っていくとxからyへのパスが得られます．

以下実装例．

[code]

    import sys
    sys.setrecursionlimit(10 ** 6)
    
    def dfs(now):
        visited[now] = True
        for nex in graph[now]:
            if visited[nex]:
                continue
            from_[nex] = now
            if nex == y:
                return
            dfs(nex)
    
    n, x, y = map(int, input().split())
    graph = [[] for _ in range(n + 1)]
    
    for _ in range(n - 1):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)
    
    visited = [False for _ in range(n + 1)]
    from_ = [None for _ in range(n + 1)]
    
    dfs(x)
    
    htap = []
    while y is not None:
        htap.append(y)
        y = from_[y]
    
    print(*reversed(htap))
    
[/code]


CC BY-SA 4.0
2022-09-25T15:54:55.870
91297
2022-09-25T19:35:42.537
2022-09-25T19:35:42.537
51374
51374
91294
answer

[code]

    # 追跡済みじゃなければ値を追加
    if i not in traced:
    
[/code]

この部分で、追跡済みかどうかを毎回線形探索しているのは効率が悪いです。今回 N が最大 200000
まで達するので、この行で繰り返し行われている探索の時間が問題になります。追跡済みかどうかをすぐ判定できるようにフラグを配列で保持するのが良いでしょう。


CC BY-SA 4.0
2022-09-25T16:06:21.230
91298
2022-09-25T16:06:21.230
19110
91294
answer