yura1685

ABC448の解法記事

C - Except and Min

パッと見計算量が厳しそうな問題ですが，$1 \le K \le 5$ と $K$ が小さいのが使えそうです．ボールを $K$ 個取り除いたあとの数列 $A$ の最小値としてありえる数は元の数列 $A$ の小さい順 $\mathrm{Best}\ K+1$ には入っているはずなので，$A$ の小さい順に $6$ 個取り出した数列だけ考えれば良いです．

I = input().split()
N, Q = int(I[0]), int(I[1])
A = list(map(int, input().split()))
minA = sorted(A)[:6]

for _ in range(Q):
    K = int(input())
    B = list(map(int, input().split()))
    s = minA.copy()
    for b in B:
        if A[b-1] in s:
            s.pop(s.index(A[b-1]))
    print(s[0])

D - Integer-duplicated Path

木のパスの状態について考えるときは DFS が刺さりますね．パス上の数と $2$ 回以上出現した数の個数を保持しながら DFS をして，ans 配列に記録していけば解くことが出来ます．

from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
G = [[] for _ in range(N)]
for _ in range(N-1):
    U, V = map(int, input().split())
    G[U-1].append(V-1)
    G[V-1].append(U-1)

count = defaultdict(int)
cnt = 0
ans = [False] * N

stack = [(0, -1, True)]
while stack:
    u, p, f = stack.pop()
    if f:
        count[A[u]] += 1
        if count[A[u]] == 2:
            cnt += 1
        if cnt > 0:
            ans[u] = True
        stack.append((u, p, False))
        for v in G[u]:
            if v != p:
                stack.append((v, u, True))

    else:
        if count[A[u]] == 2:
            cnt -= 1
        count[A[u]] -= 1

for a in ans:
    print('Yes' if a else 'No')

E - Simple Division

まず $\big\lfloor \frac{N}{M} \big\rfloor \pmod {10007}$ ですが，これは典型として $N \pmod {M\times 10007}$ を $M$ で割った商に等しいですね．肝心のレピュニット数についてですが，$\frac{10^n-1}{9}$ としてしまうと $\gcd(9, M\times 10007) > 1$ のときに非常にややこしくなってしまうので $\begin{pmatrix} a_{n+1} \ 1 \end{pmatrix} = \begin{pmatrix} 10 & 1 \ 0 & 1 \end{pmatrix} \times \begin{pmatrix} a_n \ 1 \end{pmatrix}$ を用いて繰り返し二乗法で計算する方が良いです．（類題1, 類題2, 類題3）

K, M = map(int, input().split())
MOD = 10007 * M

def f(r, n, mod):
    res = 0
    sum = 1
    pow = r
    while n > 0:
        if n % 2 == 1:
            res = (res * pow + sum) % mod
        sum = sum * (1 + pow) % mod
        pow = pow ** 2 % mod
        n //= 2
    return res

ans = 0
for _ in range(K):
    c, l = map(int, input().split())
    hoge = c * f(10, l, MOD) % MOD
    ans = (ans * pow(10, l, MOD) + hoge) % MOD

print(ans // M)