0

以下問題についてです。

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

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

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

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

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()
1
  • 3
    必須というわけではありませんが、質問はなるべく自己完結していると嬉しいです。リンクが切れても Q&A の質を保ちやすいからです。今回の場合ですと、ざっくりとで良いのでどういう問題をどういう方針で解こうとしたのかが書かれていると嬉しいです。
    – nekketsuuu
    Commented 2022年9月25日 15:53

2 件の回答 2

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

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

1

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

参考:
Python - TimeComplexity


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

以下実装例.

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))

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。