AtCoder Beginner Contest 213 参戦記

久々の3桁順位、やった!

ABC213A - Bitwise Exclusive Or

1分半で突破. 書くだけ.

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

print(A ^ B)

ABC213B - Booby Prize

3分で突破. 書くだけ.

N, *A = map(int, open(0).read().split())

print(sorted(enumerate(A), key=lambda x: x[1])[-2][0] + 1)

ナチュラルにインデックス付きソートをしてしまいましたが、今回に関して言えば不要ですね.

N, *A = map(int, open(0).read().split())

b = sorted(A)[-2]
print(A.index(b) + 1)

ABC213C - Reorder Cards

11分で突破. H,W≦10⁹ なので迂闊なことをすると MLE, TLE が待っている. とはいえ、縦方向と横方向で2回座圧するだけと考えれば簡単.

from sys import stdin

readline = stdin.readline

H, W, N = map(int, readline().split())

a = set()
b = set()
c = []
for i in range(N):
    A, B = map(int, readline().split())
    a.add(A)
    b.add(B)
    c.append((A, B))

aa = {}
for i, v in enumerate(sorted(a)):
    aa[v] = i + 1
bb = {}
for i, v in enumerate(sorted(b)):
    bb[v] = i + 1

result = []
for x, y in c:
    result.append('%d %d' % (aa[x], bb[y]))
print(*result, sep='\n')

ABC213D - Takahashi Tour

9分で突破. 小さい順にを高速に実現するために優先度付きキューを使うということだけ分かっていれば、後は問題文のとおりに DFS するだけなのでそこまで難しくはない.

from heapq import heappop, heappush
from sys import setrecursionlimit, stdin

readline = stdin.readline
setrecursionlimit(10 ** 6)

N = int(readline())

links = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    A, B = map(int, readline().split())
    heappush(links[A], B)
    heappush(links[B], A)


def dfs(n):
    result.append(n)
    visited.add(n)
    while links[n]:
        i = heappop(links[n])
        if i in visited:
            continue
        dfs(i)
        result.append(n)


visited = set()
result = []
dfs(1)
print(*result)

よくよく考えると途中追加がないので優先度付きキューは要らなかった.

from sys import setrecursionlimit, stdin

readline = stdin.readline
setrecursionlimit(10 ** 6)

N = int(readline())

links = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    A, B = map(int, readline().split())
    links[A].append(B)
    links[B].append(A)

for l in links:
    l.sort(reverse=True)

def dfs(n):
    result.append(n)
    visited.add(n)
    while links[n]:
        i = links[n].pop()
        if i in visited:
            continue
        dfs(i)
        result.append(n)


visited = set()
result = []
dfs(1)
print(*result)

ABC213E - Stronger Takahashi

50分で突破. 時間かかりすぎですね. 1×1なら01BFSで行けるのだが、2×2となるとそうは行かない. 下手にやると1回のパンチで済むところを2回にしてしまいそうだなあと悩み、パンチが不要な移動とパンチによる移動を完全に分離すればいいと思いついた.

from collections import deque

INF = 10 ** 15

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

dp = [[INF] * W for _ in range(H)]
dp[0][0] = 0
q1 = deque([(0, 0)])
q2 = deque([])
while q1:
    while q1:
        y, x = q1.popleft()
        for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ny, nx = y + dy, x + dx
            if ny < 0 or ny >= H or nx < 0 or nx >= W:
                continue
            if S[ny][nx] == '.':
                if dp[ny][nx] <= dp[y][x]:
                    continue
                dp[ny][nx] = dp[y][x]
                q1.append((ny, nx))
            elif S[ny][nx] == '#':
                if dp[ny][nx] <= dp[y][x] + 1:
                    continue
                dp[ny][nx] = dp[y][x] + 1
                q2.append((ny, nx))
    while q2:
        y, x = q2.popleft()
        for dy, dx in [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]:
            ny, nx = y + dy, x + dx
            if ny < 0 or ny >= H or nx < 0 or nx >= W:
                continue
            if dp[ny][nx] <= dp[y][x]:
                continue
            dp[ny][nx] = dp[y][x]
            q1.append((ny, nx))
print(dp[H -1][W - 1])