AtCoder ABC417 振り返り(PythonでABC+E問題)

ABC417を振り返ります

今回はABCまで3問解答でした。レーティングは微減でした。

A問題で7分くらいかかってしまったのが若干痛かったです。その後、C問題まではスムースに行けたのですが、D問題が難しかったです。
E問題に取り組んで、DFS(深さ優先探索)を使う発想はあっていたのですが、ちょっと分かってなかったところがあり、時間切れとなりました。

A - A Substring

Pythonなら S[A:-B] みたいに書けば楽勝...と思ったらそうでもなかったです。入力例2のような、1文字のときに誤答となってしまいます。
結局、for文で解きました。

N, A, B = map(int, input().split())
S = list(input())

# AからN-Bまでの文字を取り出す
answer = []
last = N - B 
for i in range(A, last):
    answer.append(S[i])

print(''.join(answer))

---

S[A:-B] でうまくいかない理由は、公式解説に書いてありました。

https://atcoder.jp/contests/abc417/editorial/13551
Python でスライスを用いて末尾から B 文字取り除いた文字列を作る際、[:-B] のような操作をすると B=0 のときに意図しない挙動となってしまうため、一工夫必要になります。
B が 1 以上になるように S の末尾に 1 文字追加したり、−B ではなく N−B でアクセスすることで意図した動作にすることができます。

なるほど...ということで、こう書けばACになります。

N, A, B = map(int, input().split())
S = input()
print(S[A:N-B])

B - Search and Delete

Bの要素に対して、配列Aから削除するという操作を行います。配列の途中の要素を削除するのはコストが大きくてTLEの原因になりやすいのですが、今回はそこまで大きい配列ではない(要素数100以下)ので大丈夫です。

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# Bの要素をAから削除する
for i in range(len(B)):
    b = B[i]

    # Aの中からBの要素を探す. もし見つかったら削除する
    for j in range(len(A)):
        if A[j] == b:
            A.pop(j)
            break
print(*A)

C - Distance Indicators

j - i == A[i] + A[j] という条件を満たすi, jの組み合わせを数える問題です。

上の式を変形すると、こうなります → j - A[j] == i + A[i] 。

ここまでできれば後は、配列 A から 配列 j_array == j - A[j] と i_array == i + A[i] をあらかじめ作成しておけば、あとはそれぞれの配列を使って条件を満たす組み合わせを数えることができます。

組み合わせの数をfor文で数えるとTLEしてしまうので、最初に
j_array の値の出現回数を辞書に記録しておけば、計算量を減らすことができます。

N = int(input())
A = list(map(int, input().split()))

j_array = [] # j - A[j] の値を記録する配列
i_array = [] # i + A[i] の値を記録する配列
j_count = defaultdict(int) # j_count[j - A[j]] の値の出現回数を記録する辞書

# 前処理: i_array と j_array を作成
for i in range(N):
    i_array.append(i+A[i])
    j_array.append(i-A[i])
    j_count[j_array[-1]] += 1


answer = 0
for i in range(N):
    # j_array[i] の値の出現回数を減らす
    j_count[j_array[i]] -= 1

    i_value = i_array[i]
    # i_value の値が j_count に存在する場合、その出現回数を答えに加える
    answer += j_count[i_value]

print(answer)

E - A Path in A Dictionary (解説AC)

惜しいところまではできたのですが、TLEしてしまいました。

ソースコードの※の行をコメントアウトするとTLEしてしまいます。※は、訪問済みのノードを元に戻す処理ですが、これを行うと無駄な探索をしてしまいます。

図のようなグラフがあって、3→5に行きたい場合を考えます。
辞書順に探すので 3→1→... を探すわけですが、その先は5にたどり着けないですね。
次に 3→2→...を探すわけですが、ここで3→2→1と行くと、先程ゴールにたどり着けなかった1の先をまた探すことになり、無駄な探索が増えてしまいます。

そのため、訪問済みのノードを消す処理は不要なのでした(この問題の場合は)。

T = int(input())

# テストケースを処理する関数
def calc():
    N, M, X, Y = map(int, input().split())

    # グラフの隣接リストを作成
    path = defaultdict(list)
    for _ in range(M):
        u, v = map(int, input().split())
        path[u].append(v)
        path[v].append(u)
    
    visited_set = set()
    visited_history = []    

    # 深さ優先探索(DFS)を定義
    def dfs(v):
        visited_history.append(v)
        visited_set.add(v)

        # 終点Yに到達した場合、DFSを終了
        if v == Y:
            return True

        # 隣接するノードを探索. ソートしているのは、辞書順に訪問するため
        for next_v in sorted(path[v]):
            if next_v not in visited_set:
                if dfs(next_v):
                    return True

        # 終点にたどり着けなかったので、訪問済みのノードを戻す
        visited_history.pop()

        # ※ここで訪問済みのノードを元に戻してしまうと、TLEになる
        # visited_set.remove(v)
        
        return False

    # 始点XからDFSを開始
    dfs(X)
    print(*visited_history)

# 各テストケースをループして処理
for i in range(T):
    calc()