【AtCoder】ABC213をPython3で解説（ABCD）

ABC213の解説。

A - Bitwise Exclusive Or

解説

xor は、排他的論理和を表す。
これについては、^ を用いることで答えがでる。

コード

a, b = map(int, input().split())

print(a ^ b)

B - Booby Prize

解説

下位から2番目の選手番号、つまり、スコアが2番目に大きい選手番号を答える問題。

enumerate()でスコアと選手番号をあわせてタプルにする。
その後、降順でソートし、リストの2番目の値を取ればAC。

コード

n = int(input())
alist = map(int, input().split())
result = []

for i, v in enumerate(alist):
    result.append((v, i+1))

ans = sorted(result, reverse=True)
print(ans[1][1])

C - Reorder Cards

解説

今回の問題は、*と数値を使って、テーブルを作ってコードを書く、のではない。
それをしてしまうと、REしてしまう。

今回は、座標圧縮という方法を用いる。座標圧縮の手順は次のとおりだ。

• 座標についてのリストを作成する
• set()で重複を取り除く
• リストに戻して昇順に並び替え（ソート）する
• 番号と座標を合わせて辞書化
• もとのリストから値を参照する

この順番にコードを記述することで、ACできる。

コード

H, W, N = map(int, input().split())
X, Y = [], []

for i in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)


Xdict = {x: i+1 for i, x in enumerate(sorted(list(set(X))))}
Ydict = {y: i+1 for i, y in enumerate(sorted(list(set(Y))))}


for i in range(N):
    print(Xdict[X[i]], Ydict[Y[i]])

D - Takahashi Tour

解説

グラフ理論の問題。

都市1をスタートして、番号が小さい順番に深さ優先探索していく。深さ優先探索には、再帰関数を用いる。

まず、都市同士のつながりをもったグラフ作りたいので、隣接行列を作成する。今回は、番号が小さい順に訪れたいので、あらかじめ各行をソートしておく。

あとは、深さ優先探索をして、訪れた都市をひとつずつリストに追加していき、出力すればAC。（この出力をオイラーツアーという。）

コード

# 再起の深さ上限を増やす
import sys
sys.setrecursionlimit(300000)

N = int(input())
graph = [[] for _ in range(N + 1)]

for i in range(N - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(N + 1): # 隣接しているもので小さい順に訪れたいので、ソート
    graph[i].sort()

ans = []

def dfs(curr, prev): # DFS（深さ優先探索）
    ans.append(curr) # 訪れたノードを追加
    for nxt in graph[curr]:
        if nxt != prev:
            dfs(nxt, curr)
            ans.append(curr)

dfs(1, -1)
print(*ans) # オイラーツアー

編集後記

D問題解説するだけでものすごく知識がついている気がす