👻

【python】100日後に緑コーダーになるためのABC213 A,B,C,D問題【13日目】

2 min read

はじめに

100日後に緑コーダーになるためにAtcoder Beginner Contest213の解説を行います。
今回はA ~ D問題です。
使用言語はpythonです。
ACコードだけでなく出題者の意図や考察過程も記述しています。
気になるところや要望があればお気軽にコメントください。
それでは解説です。

対象読者

灰・茶コーダー

A - Bitwise Exclusive Or

https://atcoder.jp/contests/abc213/tasks/abc213_a

解法

全探索

出題者の意図

排他的論理和に惑わされず全探索できるか

コード

A , B = map(int, input().split())
for i in range(256):
    if A ^ i == B:
        print(i)

B - Booby Prize

https://atcoder.jp/contests/abc213/tasks/abc213_b

解法

元の最大値を削除して答えのインデックスを探索

出題者の意図

工夫して探索できるか

コード

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

https://atcoder.jp/contests/abc213/tasks/abc213_c

解法

座標圧縮して二分探索

出題者の意図

座標圧縮できるか

考察

全行・全列を調べていくと当然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

https://atcoder.jp/contests/abc213/tasks/abc213_d

解法

深さ優先探索

出題者の意図

深さ優先探索の仕組を理解しているか

考察

深さ優先探索の探索方法そのままである。

コード

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

ログインするとコメントできます