😎

AtCoder ABC212 個人的メモ

2021/08/01に公開

Python

競技プログラミング

AtCoder

tech

所感

abcd4完

A - Alloy

問題文通りに実装

A, B = map(int, input().split())

if 0 < A and B == 0:
    print("Gold")
elif A == 0 and 0 < B:
    print("Silver")
elif 0 < A and 0 < B:
    print("Alloy")

B - Weak Password

公式解説見て書き直した

A = list(map(int, input()))

if len(set(A)) == 1 or all((A[i] + 1) % 10 == A[i + 1] % 10 for i in range(3)):
    print("Weak")
else:
    print("Strong")

C - Min Difference

各 $A_i$ における最適な $B_j$ は $A_i$ に最も近い数。
それは2分探索すれば求まる。

from bisect import bisect_left

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

B.sort()
ans = 10 ** 18
for a in A:
    i = bisect_left(B, a)
    for di in (-1, 0, 1):
        ni = i + di
        if 0 <= ni < M:
            ans = min(ans, abs(a - B[ni]))

print(ans)

操作2の「袋に入っているすべてのボールについて、 $X_i$ を加える」という操作を「これから袋に入れる全てのボールにつて $X_i$ を引く」と言い換える。
また、操作3も「取り出したボールに書かれている数を記録する」という操作を「取り出したボールにそれまで引いた数を加算した数を記録する」と言い換える。
後は操作3の時に袋内の最小値を求めればおｋ。
毎度最小値を求めるとTLEしそうなので優先度付きキューを使う。

from heapq import heappop, heappush

Q = int(input())
priority_queue = []
ans = []
dec = 0
for _ in range(Q):
    P, *X = map(int, input().split())
    if P == 3:
        ans.append(heappop(priority_queue) + dec)
        continue
    X = X[0]
    if P == 2:
        dec += X
    if P == 1:
        heappush(priority_queue, X - dec)

print(*ans, sep="\n")

E - Safety Journey

$dp[i][j]$ を始点が頂点 $1$ で終点が頂点 $j$ かつ距離 $i$ のパスが何個あるか？とする。
頂点 $j$ と隣接している頂点の集合を $S$ とすると、遷移は以下のようになる。

dp[i+1][j]=\sum_{k\in S}dp[i][k]

これだと計算量が $O(KN^2)$ となりTLEする。
制約を見ると $0\leq M\leq min(\frac{N(N-1)}{2},5000)$ とある。
$\frac{N(N-1)}{2}$ は問題文の条件下での全ての辺の個数を示している。
だからこの制約は頂点数が大きい場合には削除される辺の個数が全体の辺の個数に対して小さいことを示している。
これを生かして頂点 $j$ と隣接していない頂点の集合を $S'$ とすると、遷移は以下のようになる。

dp[i+1][j]=\sum_{k=0}^Ndp[i][k]-\sum_{k\in S'}dp[i][k]

$\sum_{k=0}^Ndp[i][k]$ は $j$ に依らず各 $i$ で同じなので、各 $i$ 当たり $O(N)$ で求まる。
$\sum_{k\in S'}dp[i][k]$ は各 $j$ ごとに計算が必要で各 $i$ 当たり $O(M+N)$ で求まる。
これは $M$ が十分に小さいので、全体として計算量が $O(N(M+N))$ となっても十分に高速となる。

EDPC-Rと似ていてdpはすぐに立式できたけれども、うまく遷移を削減できなかった。
制約も見たけど $M\leq 5000$ の意味をきちんと理解できてなかった。

N, M, K = map(int, input().split())
no_edge = [[i] for i in range(N)]
for _ in range(M):
    x, y = map(lambda n: int(n) - 1, input().split())
    no_edge[x].append(y)
    no_edge[y].append(x)  # 有向グラフならこの行は消す!!
MOD = 998244353

dp = [0] * N
dp[0] = 1
for k in range(K):
    n_dp = [sum(dp) % MOD] * N
    for t in range(N):
        for s in no_edge[t]:
            n_dp[t] -= dp[s]
        n_dp[t] %= MOD
    dp = n_dp

print(dp[0])