Zenn
🙌

【python】100日後に緑コーダーになるためのABC209 C,D問題【2日目】

2021/11/24に公開
Python
AtCoder
競プロ
tech

はじめに

100日後に緑コーダーになるためにAtcoder Beginner Contest225の解説を行います。
今回はC,D問題です。
使用言語はpythonです。
ACコードだけでなく出題者の意図や考察過程も記述しています。
気になるところや要望があればお気軽にコメントください。
それでは解説です。

対象読者

灰・茶コーダー

C - Calendar Validator

https://atcoder.jp/contests/abc225/tasks/abc225_c

解法

カレンダーの中に入っているか判定

出題者の意図

カレンダーの問題を解けるか
特殊なケースが気付けるか

コード

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

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

if M == 1:
    for i in range(N-1):
        if B[i][0]+7 != B[i+1][0]:
            print('No')
            exit()
if N == 1:
    for j in range(M-1):
        if B[0][j]+1 != B[0][j+1]:
            print('No')
            exit()           
        if (B[0][j]-1)%7+1 != (B[0][j+1]-1)%7:
            print('No')
            exit()


for i in range(N-1):
    if B[i][0]+7 != B[i+1][0]:
        print('No')
        exit()
    for j in range(M-1):
        if B[i][j]+1 != B[i][j+1]:
            print('No')
            exit()           
        if (B[i][j]-1)%7+1 != (B[i][j+1]-1)%7:
            print('No')
            exit()

print('Yes')

D - Play Train

https://atcoder.jp/contests/abc225/tasks/abc225_d

解法

連結リストで管理して、深さ優先探索

出題者の意図

連結リストを管理できるか
簡単な深さ優先探索を実装できるか

考察

電車が連結するときは直列しかないので連結リストで管理しやすそうです。
連結リストのi番目の電車に繋がった電車を記憶させます。
0列目が前にいる電車、1列目が後ろにいる電車です。
繋がっていないときは-1にしておきましょう。
クエリ3で連結した電車は深さ優先探索を使います。

コード

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

train = [[-1,-1] for _ in range(N+1)]
for _ in range(Q):
    query = list(map(int,input().split()))
    if query[0] == 1:
        x,y = query[1],query[2]
        train[x][1], train[y][0] = y,x
    elif query[0] == 2:
        x,y = query[1],query[2]
        train[x][1], train[y][0] = -1,-1
    else:
        x = query[1]
        front = []
        back = []
        f = train[x][0]
        b = train[x][1]
        while f != -1:
            front.append(f)
            f = train[f][0]
        while b != -1:
            back.append(b)
            b = train[b][1]
        ans = front[::-1] + [x] + back
        print(len(ans), *ans)

Discussion