ABC 311 備忘録

概要

　今回はABC311（2023年7月23日（土）21:00~22:40）についてポイントと自分の実装について書いていきたいと思う。

A問題

ポイント

• 'A', 'B', 'C' について文字数のカウントをそれぞれ行う

自分の実装

ABC_311_A.py

N = int(input())

S = input()

ans = 0

count_ABC = [0, 0, 0]

for i in range(N):
    ans += 1
    if S[i] == 'A':
        count_ABC[0] += 1
    elif S[i] == 'B':
        count_ABC[1] += 1
    else:
        count_ABC[2] += 1
    if count_ABC[0] >= 1 and count_ABC[1] >= 1  and count_ABC[2] >= 1:
        print(ans)
        exit()

B問題

ポイント

• 各日にちについて各々のスケジュールを確認するので、入力を numpy の2次元配列として格納
• 'numpy' の列ごとに ['o','o','o', ...]と一致するかどうかを判定
• 連続して上の判定式が True となるかを確認
• 連続が終了したら、その時点で連続日数を記録・リセット

自分の実装

ABC_311_B.py

import numpy as np

N, D = map(int, input().split())

S = np.array(list(list(input()) for i in range(N)))

free = np.array(['o' for i in range(N)])
ans = 0
continuous = True
count_continuous = 0

for i in range(D):
    S_line = S[:, i]
    if np.array_equal(S_line, free):
        continuous = True
        count_continuous += 1
    else:
        ans = max(ans, count_continuous)
        continuous = False
        count_continuous = 0

ans = max(ans, count_continuous)

print(ans)

C問題

ポイント

• 有向グラフの閉路検出を行えば良い
• すでに訪れたことのあるノードに達した時点で閉路を返す

自分の実装

ABC_311_C.py

def find_cycle(graph, start):
    stack = [start]
    visited = [False] * (len(graph) + 1)
    while stack:
        current = stack[-1]
        if visited[current]:
            return stack[stack.index(current):]
        visited[current] = True
        next_node = graph[current]
        stack.append(next_node)
    return None

def main():
    N = int(input())
    A = [0] + list(map(int, input().split()))  # 0番目の要素は無視するため0を追加

    cycle = find_cycle(A, 1)  # 頂点1をスタートとして有向閉路を探索

    if cycle:
        M = len(cycle)
        print(M-1)
        print(*cycle[0:-1])
    else:
        print("No cycle found.")

if __name__ == "__main__":
    main()

感想

　C問題まで解けたが、相変わらずDFS・BFSの実装について全然慣れていなかったので、勉強が必要だと思った、D問題についてもDFSで解けるはずなので解き直したい。