AtCoder Beginner Contest 198

A〜Cに回答できました．Dまで回答したいところでした．

A - Div

$N$個の○の間に|を入れる方法の数＝$N-1$．

B - Palindrome with leading zeros

$N$は最大9桁なので，ゼロを先頭に0~9つけたうえで文字列を反転させて比較すればよい．文字列Aを反転させる方法は

A[::-1]

C - Compass Walking

最短距離は$d=\sqrt{X^{2}+Y^{2}}$．直線で$r$より小さくなる1歩前まで近づいて，最後の2歩でぴったりになるよう調整すればよい．

つまり（$d\geq r$のとき）

• $d$が$r$で割り切れる場合：「$d/r$の商」
• $d$が$r$で割り切れない場合：「$d/r$の商-1+2」

となる．これは，$d/r$を切り上げて整数にしたもの（$=\lceil d/r \rceil$）と表現できる．Python では

math.ceil(d/r)

とかける．

$d < r$のときが例外で2歩となる．

D - Send More Money

文字列をsetに入れて，全ての場合を生成して判定すれば良いところまではわかりました．ポイントは次です．①1つめを見落としていた，②処理が遅くTLEとなったことから時間内に回答できませんでした．
【ポイント】

• $N_{i}^{\prime}$は正で$S_{i}$の文字列に等しい$\Leftrightarrow N_{i}^{\prime}$の1文字目$\neq$0．
• $S_{1},S_{2},S_{3}$に含まれる文字種は$10\,(0\sim 9)$以下．

例えば，次がわかりやすい：Submission #21649960 - AtCoder Beginner Contest 198

E - Unique Color

グラフのことを知らなすぎて，コードを読んでもわかりません．
→2021.04.24：蟻本で隣接リストの使い方を学んで，理解できるようになりました（Pythonで蟻本2-5 - グラフ - 競プロはじめました）．

参考になるコードにコメントを加えて書き直しました．

# https://atcoder.jp/contests/abc198/submissions/21656222
import sys
sys.setrecursionlimit(500005)

n = int(input())
c = list(map(int, input().split()))
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = list(map(int, input().split()))
    g[a-1].append(b-1)
    g[b-1].append(a-1)

def dfs(cur, pre, g, f, c):
    """
    current(現在地), previous(前いた点),
    graph(隣接リスト), f(経路上にあった色)
    c(各頂点の色リスト)
    """
    if f[c[cur]] == 0:
        ans.append(cur+1)
    f[c[cur]] += 1
    
    # 前いた頂点を除く隣接頂点でdfs
    # 最短経路で最も早く各頂点の色が記録される
    # →最短でない場合は上のifで落ちる
    for e in g[cur]:
        if e != pre:
            dfs(e, cur, g, f, c)
    # dfsから出ていく(頂点curから出ていく)ときは
    # 経路上の色リストから消す
    f[c[cur]] -= 1

ans = []    
dfs(0, -1, g, [0]*(100001), c)
ans.sort()
for v in ans:
    print(v)

これも気になります：Submission #21651950 - AtCoder Beginner Contest 198

F - Cube