ABC342をPythonで（A～E）

HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）の解答等のまとめ

A問題

1文字なのが何か求めて、そのインデックスを出力

A

s = input()
t = sorted(list(s))
diff = t[-1] if t[0] == t[1] else t[0]

print(s.index(diff) + 1)

B問題

全探索しても間に合うので、$a$と$b$のインデックスを毎回調べて答えればよい

B

n = int(input())
p = list(map(int, input().split()))

for _ in range(int(input())):
    a, b = map(int, input().split())
    print(a if p.index(a) < p.index(b) else b)

C問題

$S$を毎回変更していては間に合わないから、最終的に各文字が何になるか調べればよい

C

n = int(input())
s = list(input())

a = {chr(ord("a") + i):{chr(ord("a") + i)} for i in range(26)}

for _ in range(int(input())):
    c, d = input().split()
    if c == d:
        continue
    a[d] |= a[c]
    a[c] = set()

dic = dict()
for key, val in a.items():
    for b in list(val):
        dic[b] = key

for i in range(n):
    s[i] = dic[s[i]]

print("".join(s))

D問題

$a_ia_j$が平方数になるには、$a_i$,$a_j$のそれぞれで素因数分解したときに奇数個の素因数が同じであればよい
あとは$0$の処理に気を付けて実装する

D

from collections import defaultdict
from functools import lru_cache

@lru_cache(maxsize=None)
def calc(x):
    res = set()
    i = 2
    while i * i <= x:
        if x % i == 0:
            count = 0
            while x % i == 0:
                count += 1
                x //= i
            if count % 2 == 1:
                res.add(i)
        i += 1

    if x > 1:
        res.add(x)

    return tuple(sorted(res))


n = int(input())
a = list(map(int, input().split()))

ans = 0
d = defaultdict(int)
zero = n - 1
for i, a_i in enumerate(a):
    if a_i == 0:
        ans += zero
        zero -= 1
    else:
        c = calc(a_i)
        ans += d[c]
        d[c] += 1

print(ans)

E問題

$N$を始点にダイクストラのように計算する

E

from heapq import heappop, heappush


def max_pop(q):
    t, x = heappop(q)
    return -t, x
def max_push(q, t, x):
    heappush(q, [-t, x])


n, m = map(int, input().split())

edge = [[] for _ in range(n)]
for _ in range(m):
    l, d, k, c, a, b = map(int, input().split())
    edge[b - 1].append([a - 1, l, d, k, c])

INF = float("inf")
time = [-1] * n
q = []
max_push(q, INF, n - 1)

while q:
    t_i, now = max_pop(q)
    if time[now] > t_i:
        continue

    for to, l, d, k, c in edge[now]:
        if t_i >= INF:
            nxt = l + d * (k - 1)
        else:
            k_to = (t_i - (l + c)) // d
            if k_to < 0:
                continue
            nxt = l + d * min(k_to, k - 1)

        if time[to] < nxt:
            time[to] = nxt
            max_push(q, nxt, to)

for i, t_i in enumerate(time[:-1]):
    print(t_i if t_i >= 0 else "Unreachable")