AtCoder ABC198 個人的メモ

所感

abc3完

A - Div

N = int(input())

print(N - 1)

B - Palindrome with leading zeros

制約が$0\leqq N \leqq 10^9$なので，最大10桁の$N$があり得る
なので，0から10個の0を先頭に足した場合それぞれにおいて回文か判定する

N = input()

ans = False
for i in range(10):
    res = "0" * i + N
    if res == res[::-1]:
        ans = True

if ans:
    print("Yes")
else:
    print("No")

C - Compass Walking

サンプルから，ユークリッド距離を$L$とした時に$\lceil \frac{L}{R}\rceil$となりそうと分かる
しかし，これだと$L\leq R$の時に解が$1$になってwaする(した)
この場合の解は2なので，そうなるようにする

from math import ceil

R, X, Y = map(int, input().split())

length = (X ** 2 + Y ** 2) ** 0.5

ans = ceil(length / R)
if length < R:
    ans += 1

print(ans)

E - Unique Color

DFSで解けそうってのはすぐ分かったのに，通った色の管理法が悪くてTLEしてた

木なので，頂点$1$からDFSをすれば全ての頂点へ最短経路で到達できる．
DFSで探索中に通った頂点の色を記録しておいて，各頂点で良い頂点かを判定すれば良さそう．
DFSの計算量は頂点数を$N$，辺の数を$M$とした時に$O(N+M)$だから，各頂点の判定は$O(1)$で行う必要がある．
そのためには，色の数字をインデックスとする配列で管理すればいい
実装にはCounterを使った
parentsを集合を使って管理するとTLEする(した)

from collections import Counter
from sys import setrecursionlimit

setrecursionlimit(10 ** 6)


def dfs(n: int, parents: dict):
    seen[n] = True
    for d in edge[n]:
        if seen[d]:
            continue
        if parents[C[d]] == 0:
            ans.add(d)
        parents[C[d]] += 1
        dfs(d, parents)
        parents[C[d]] -= 1
    return


N = int(input())
C = [0] + list(map(int, input().split()))
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)

seen = [False] * (N + 1)
ans = {1}
dfs(1, Counter([C[1]]))
print(*sorted(ans), sep="\n")