👏

AtCoder ABC213 個人的メモ

2021/08/09に公開

Python

競技プログラミング

AtCoder

tech

所感

abcd4完
3wa
waが多すぎる

A - Bitwise Exclusive Or

$C$ を0から順に $A\ \textrm{xor}\ C=B$ となるか調べていけばおｋ

$C$ が1以上と誤読して1wa

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

for C in range(300):
    if A ^ C == B:
        break

print(C)

B - Booby Prize

$A$ をソートすればブービー賞に該当する選手のスコアが分かる。
後はそのスコアの選手の番号が分かれば良い。
制約よりスコアは全て異なるので、あるスコアと対応する選手の番号は1つ。
なので、適当に両者を結びつけてメモして置けば良い。

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

lst = [(a, i) for i, a in enumerate(A, start=1)]
lst.sort()
print(lst[-2][1])

C - Reorder Cards

座標圧縮

x,yのそれぞれの座標が同一の場合を考慮し忘れて1wa(a_S,b_Sを集合内包表記でなくてリスト内包表記で書いてた)

H, W, N = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(N)]

a_S = sorted({a for a, _ in lst})
a_trans = {a: i for i, a in enumerate(a_S, start=1)}
b_S = sorted({b for _, b in lst})
b_trans = {b: i for i, b in enumerate(b_S, start=1)}
for a, b in lst:
    print(a_trans[a], b_trans[b])

D - Takahashi Tour

オイラーツアー

移動先の都市の番号が小さい順になるようにしていなくて1wa(edge配列のソートしてなかった)

from sys import setrecursionlimit

setrecursionlimit(10 ** 7)


def rec(now: int):
    if seen[now]:
        return
    seen[now] = 1
    ans.append(now + 1)
    for n_node in edge[now]:
        if seen[n_node]:
            continue
        rec(n_node)
        ans.append(now + 1)
    return


N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N - 1):
    x, y = map(lambda n: int(n) - 1, input().split())
    edge[x].append(y)
    edge[y].append(x)
edge = [sorted(res) for res in edge]

seen = [0] * N
ans = []
rec(0)

print(*ans)

E - Stronger Takahashi

堀のマスから道のマスへの移動が可能とする。
この時、(コスト1でパンチをして現在地に隣接する $2\times 2$ の塀を壊す)=(コスト1で現在地に隣接する $2\times 2$ の範囲にワープする)と言い換えることができる。
なので、これを01BFSやダイクストラ法で実装すればおｋ。
ダイクストラの場合は枝刈りしないとTLEする(した)。

from collections import deque

H, W = map(int, input().split())
S = [input() for _ in range(H)]
INF = 10 ** 18

seen = [[INF] * W for _ in range(H)]
queue = deque([(0, 0, 0)])
while queue:
    # cntはワープした回数(パンチ)
    i, j, cnt = queue.popleft()
    if seen[i][j] < cnt:
        continue

    # ワープしない場合
    for di, dj in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
        ni = i + di
        nj = j + dj
        if 0 <= ni < H and 0 <= nj < W and seen[ni][nj] > cnt and S[ni][nj] == ".":
            seen[ni][nj] = cnt
            queue.appendleft((ni, nj, cnt))

    # ワープする場合
    for di in range(-2, 3):
        for dj in range(-2, 3):
            if abs(di) + abs(dj) > 3:
                continue
            ni = i + di
            nj = j + dj
            if 0 <= ni < H and 0 <= nj < W and seen[ni][nj] > cnt + 1:
                seen[ni][nj] = cnt + 1
                queue.append((ni, nj, cnt + 1))

print(seen[-1][-1])

参考

01BFS

ダイクストラ