EAFP

~ Easier to Ask for Forgiveness than Permission ~

Atcoder-ABC225をpythonで解いてみた

Atcoder 競技プログラミング

目的

  • Atcoderで上を目指すべく頑張っている中でABC225を解いたので、解説してみる
    • pypy7.3を使って解いている

A問題

atcoder.jp

考察

  • 問題文通りに解けば良い

実装

from itertools import permutations

S = list(input())
ans = set([])

for s1, s2, s3 in permutations(S):
    ans.add("".join([s1, s2, s3]))

print(len(ans))

結果

B問題

atcoder.jp

考察

  • 問題文通りに解けば良い

実装

N = int(input())

edge = [[] for _ in range(N)]
flag = False
for _ in range(N-1):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

for i in range(N):
    n = len(edge[i])
    if n == N-1:
        flag = True

if flag:
    print("Yes")
else:
    print("No")

結果

C問題

atcoder.jp

考察

  • 矩形の左上を求めれば良さそう
    • divmod 使って余りと、商を求めて使えば良さそう

2回WAを出してしまう

  • 7 8 みたいなケースを見落としていた
    • 配列の右端を見る条件を追加した

実装

N, M = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(N)]

cnt_i, cnt_j = divmod(B[0][0], 7)
flag = True

if cnt_i == 0 and cnt_j == 0:
    flag = False
else:
    if cnt_j == 0:
        cnt_i -= 1
        cnt_j = 7
    for i in range(N):
        for j in range(M):
            if 7*(cnt_i+i) + (cnt_j+j) != B[i][j] or cnt_j+j > 7:
                flag = False
                break

if flag:
    print("Yes")
else:
    print("No")

結果

D問題

atcoder.jp

考察

Cに時間かかってしまったのもあるが、条件を見落としに気付くのが遅かったのも敗因

  • N,Q<=105 なので、辺を繋いだ後に、DFSやBFSをすると間に合わないと思った

    • 3 x の形式のクエリで出力する電車の番号の個数の合計は 10^6以下 という制約を見逃していた
    • UnionFindで頑張ろうと考えていたが、結合と、分離の処理が混在しており無理だった
      • アルゴリムの性質に関する理解が甘く、「なんか上手くやる方法がないか？」考えてしまった

  • DFS/BFSで経路探索するにせよ、 「電車の番号を、先頭から順番に全て出力する」 という制約に注意する必要がある

    • 無向グラフで辺を貼って、探索するとどっちが先頭かわからなくなる
    • 単に有向グラフで探索するだけだと、前にある車両の探索ができない・・・

  • そのため、「連結している前の車両」と「連結している後ろの車両」のそれぞれのnode/edgeを保持する

    • その上で探索を実施する
    • 連結する列車は1つで、辺は1つしか張られないので、消すときのコストも低い
    • 探索される車両の合計も出てるので、間に合うはず(計算回数は、106以下になる)

実装

from collections import deque

N, Q = map(int, input().split())
front, back = [0]*(N+1), [0]*(N+1)
ans = []

for _ in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 3:
        x = query[1]
        cnt = deque([x])
        cur = x
        while front[cur] != 0:
            cur = front[cur]
            cnt.appendleft(cur)
        cur = x
        while back[cur] != 0:
            cur = back[cur]
            cnt.append(cur)
        cnt.appendleft(len(cnt))
        ans.append(cnt)
    else:
        q, x, y = query
        if q == 1:
            front[y], back[x] = x, y
        else:
            front[y], back[x] = 0, 0

for i in range(len(ans)):
    print(*ans[i])

結果

まとめ

  • 今回もD解けず、rateあがらず・・・

    • 今回は問題文の見落としが大きかったので、ショックな部分もあった
      f:id:kazu_0716:20211106021354p:plain
      ABC225の結果

  • 腐らず1日1AC続けてる