ABC409をPythonで（A～E）

AtCoder Beginner Contest 409の解答等の速報的まとめ

A問題

問題文のままシミュレーションする

A

n = int(input())
t = input()
a = input()

print("Yes" if any(t_i == a_i == "o" for t_i, a_i in zip(t, a)) else "No")

B問題

配列の個数が最大 100 なので答えの最大値も 100
よって問題文の条件を満たす数を 0~100 まで全探索する

B

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(101):
    count = sum(a_i >= i for a_i in a)
    if count >= i:
        ans = max(ans, i)

print(ans)

C問題

そもそもLが3の倍数でなければ正三角形はできない。
点がどこに何個あるか求めた後、正三角形になる組み合わせを個数の積で求める

C

from collections import defaultdict

n, l = map(int, input().split())
D = list(map(int, input().split()))

d = defaultdict(int)
d[0] = 1
now = 0
for d_i in D:
    now += d_i
    now %= l
    if now not in d:
        d[now]= 0
    d[now] += 1

if l % 3 != 0:
    exit(print(0))
ans = 0
for i in range(l // 3):
    j = i + l // 3
    k = j + l // 3
    ans+= d[i] * d[j] * d[k]

print(ans)

D問題

$l$になる個所は最初に順番が逆になる個所（xa のような所）
$r$になる個所は$l$の対象の文字の後の文字が来る場所（$s_l=x$ かつ $s_r = z$）

D

for _ in range(int(input())):
    n = int(input())
    s = input()

    if n == 1:
        print(s)
    else:
        l = n - 1
        for i in range(n - 1):
            if ord(s[i]) > ord(s[i + 1]):
                l = i
                break
        r = n
        for i in range(l + 1, n):
            if ord(s[l]) < ord(s[i]):
                r = i
                break

        print(s[:l] + s[l + 1:r] + s[l] + s[r:])

E問題

各辺において一方から他方へ移動する電子（陽電子）の個数は、辺の一方にある電子と陽電子の個数差と一致する
すなわち葉から順番に電子・陽電子を移動させながら必要なエネルギーを求めていけばよい

E

from collections import deque

n = int(input())
x = list(map(int, input().split()))
edge = [list() for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    edge[u].append([v, w])
    edge[v].append([u, w])

q = deque()
q.append([0, -1])
count = [-1] * n
parent = [[0, 0] for _ in range(n)]
while q:
    now, old = q.popleft()
    for to, w_i in edge[now]:
        count[now] += 1
        if old == to:continue
        else:
            parent[to] = [now, w_i]
            q.append([to, now])

ans = 0
node = deque()
for i in range(n):
    if count[i] == 0:
        node.append(i)
while node:
    now = node.popleft()
    p, w_i = parent[now]
    # print(now, p, w_i, x[now], x[p])
    ans += abs(x[now]) * w_i
    x[p] += x[now]
    x[now] = 0
    count[p] -= 1
    if count[p] == 0:
        node.append(p)

print(ans)