AtCoder Beginner Contest 213 参戦記

# AtCoder Beginner Contest 213 参戦記

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

## [ABC213A - Bitwise Exclusive Or](https://atcoder.jp/contests/abc213/tasks/abc213_a)

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

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

print(A ^ B)
```

## [ABC213B - Booby Prize](https://atcoder.jp/contests/abc213/tasks/abc213_b)

3分で突破. 書くだけ.

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

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

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

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

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

## [ABC213C - Reorder Cards](https://atcoder.jp/contests/abc213/tasks/abc213_c)

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

```python
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](https://atcoder.jp/contests/abc213/tasks/abc213_d)

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

```python
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)
```

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

```python
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](https://atcoder.jp/contests/abc213/tasks/abc213_e)

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

```python
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])
```