📝

AtCoder ABC198 個人的メモ

2021/04/11に公開約1,900字

所感

abc3完
abc198

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")

Discussion

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