👻
【python】100日後に緑コーダーになるためのABC213 A,B,C,D問題【13日目】
はじめに
100日後に緑コーダーになるためにAtcoder Beginner Contest213の解説を行います。
今回はA ~ D問題です。
使用言語はpythonです。
ACコードだけでなく出題者の意図や考察過程も記述しています。
気になるところや要望があればお気軽にコメントください。
それでは解説です。
対象読者
灰・茶コーダー
A - Bitwise Exclusive Or
解法
全探索
出題者の意図
排他的論理和に惑わされず全探索できるか
コード
A , B = map(int, input().split())
for i in range(256):
if A ^ i == B:
print(i)
B - Booby Prize
解法
元の最大値を削除して答えのインデックスを探索
出題者の意図
工夫して探索できるか
コード
N = int(input())
A = list(map(int,input().split()))
B = A.copy()
B.remove(max(B))
ans = A.index(max(B))+1
print(ans)
C - Reorder Cards
解法
座標圧縮して二分探索
出題者の意図
座標圧縮できるか
考察
全行・全列を調べていくと当然TLEする
問題文を読むと、与えられた行と列以外は必要ないので小さい順に並べたの際のインデックスを答えればいいことに気付く。
座標圧縮したクエリのインデックスを二分探索
H,W,N = map(int,input().split())
card=[]
for _ in range(N):
a,b = map(int,input().split())
card.append([a,b])
####座標圧縮####
X = set()
Y = set()
X_index = {}
for x,y in card:
X.add(x)
Y.add(y)
X = sorted(X)
Y = sorted(Y)
for idx, x in enumerate(X):
X_index[x] = idx
from bisect import bisect_left
for c,d in card:
idxh = bisect_left(X,c)+1
idxw = bisect_left(Y,d)+1
print(idxh,idxw)
D - Takahashi Tour
解法
深さ優先探索
出題者の意図
深さ優先探索の仕組を理解しているか
考察
深さ優先探索の探索方法そのままである。
コード
N = int(input())
from heapq import heappop, heappush
#隣接リスト作成
G = [[] for _ in range(N)]
for i in range(N-1):
A, B = map(int, input().split())
heappush(G[A-1],(B-1))
heappush(G[B-1],(A-1))
ans = []
seen = [False]*N
def dfs(s):
ans.append(s+1)
seen[s] = True
while G[s]:
nxt = heappop(G[s])
if not seen[nxt]:
dfs(nxt)
ans.append(s+1)
return
dfs(0)
print(*ans)
Discussion