AtCoder ABC378 復習(緑コーダーがPythonでA〜D問題まで)

ABC378 感想まとめ

AtCoder Beginner Contest 378 - AtCoder

今回は久々にリアルタイム参加です。ただ、急に気温が寒くなってちょっと体調を崩してしまい、コンテスト前も腹痛があったので、Unratedで参加しました。

結果は、案の定、A問題で1ペナ。B問題でもかなり悩んで、時間を使ってしまいました。また、D問題は解法がわかっていたのだけど、実装方針でミスって未解答...。というわけで、もしRated参加だったら約450パフォ相当で、かなりレーティングが落ちていた模様。

Unrated参加で良かった...。

A - Pairing

問題文の通り、現れた文字をsetで覚えておいて、2回現れたらsetから削除します。
最後に、setから削除した回数を答えとして出力します。

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

# 出現した文字を保持するset
a_set = set()
a_set.add(A[0])

count = 0
for i in range(1, len(A)):
    if A[i] in a_set:
        # すでに文字があれば、文字setから削除
        a_set.remove(A[i])

        # 重複文字カウント 
        count += 1
    else:
        a_set.add(A[i])
print(count)

問題文のとおりにやれば解けるのだが、ややこしく考えて1ミスしてしまいました...

B - Garbage Collection

これも解けるには解けたのだが、時間がかかってしまった。

反省点として、変数名の付け方が良くなかったかもしれない。
問題文からして t, d, q ,r と4つの値が出てくるが、これのどれが何なのかがいまいちわかりにくい。
type, day... のように変数名をつけるほうが、パット見わかりやすそうでした (q, r がなんの略かわからない...)。

N = int(input())
QR = []
for i in range(N):
    QR.append(list(map(int, input().split())))

# Queryを処理
Q = int(input())
for i in range(Q):
    # t番目のゴミ を d日目に出した
    t, d = map(int, input().split())

    # t番目のゴミのデータ
    q, r = QR[t - 1]

    amari = d % q
    if amari == r:
        # 条件に一致しているので、当日に収集される
        print(d)
    else:
        # 次の収集日に収集される
        N = d // q
        if amari > r: # 余りが r より大きい場合は、次のターンになる
            N += 1

        print(N * q + r)

C - Repeating

配列Aを順番に探査していきます。
Aの中で値が前回出現した位置を、defaultdict に記録しておきます。
次に同じ値が出てきたときに、前回はどの位置だったのかを簡単に知ることができます。

from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
B = [-1] * N

appear_dict = defaultdict(int)
for i in range(N):
    a = A[i]
    if a in appear_dict:
        # 出現済の場合
        B[i] = appear_dict[a]
    else:
        # 未出現の場合
        B[i] = -1

    # 出現した位置を記録
    appear_dict[a] = i + 1

print(*B)

D - Count Simple Paths

深さ優先探索を使って、地図を探索します。という解法はわかったのですが、実装をミスってしまい試験時間内には解けずでした。

そもそも、dequeを使って深さ優先探索を実装しようとしていたのが良くなかった（練習ではいつも再帰関数を使って実装していたのに）。

コンテスト参加が久々だったこともあり、色々忘れているなあ...というのが反省点ですね。
以下のソースコードは、コンテスト終了後に書き直したものです。

sys.setrecursionlimit(10 ** 8)

H, W, K = map(int, input().split())
S = []

# 周りを # で囲むことで、簡単に考えられる
S.append("#" * (W + 2))
for i in range(H):
    S.append( "#" + input() + "#")
S.append("#" * (W + 2))

# 訪問済みのマスを管理
visited = [[False] * (W + 2) for i in range(H + 2)]
visit_count = 0

# 深さ優先探索
def search(i, j, cost):
    global visit_count, visited

    # ちょうど K 回の移動に成功した場合
    if cost == K:
        visit_count += 1
        return

    MOVES = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 上下左右の移動先パターン
    for move in MOVES:
        # 移動可能で、未訪問の場合は更に探索する
        if S[i + move[0]][j + move[1]] == "." and not visited[i + move[0]][j + move[1]]:
            visited[i + move[0]][j + move[1]] = True
            search(i + move[0], j + move[1], cost + 1)
            visited[i + move[0]][j + move[1]] = False   # 後続のDFSに影響を与えないようにする

    # i, j から先は探索を終えたので、後続のDFSに影響を与えないようにFalseを設定
    visited[i][j] = False


# スタート位置を変えて、探索する
for start_i in range(1, H + 1):
    for start_j in range(1, W + 1):

        # スタート地点が壁の場合はスキップ
        if S[start_i][start_j] == "#":
            continue

        # visitedをリセット
        for i in range(H + 2):
            for j in range(W + 2):
                visited[i][j] = False

        # スタート地点を訪問済みにする
        visited[start_i][start_j] = True

        # 深さ優先探索
        search(start_i, start_j, 0)

print(visit_count)