😎

AtCoder ABC212 個人的メモ

3 min read

所感

abcd4完

https://atcoder.jp/users/m193/history/share/abc212

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_jA_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)

D - Querying Multiset

操作2の「袋に入っているすべてのボールについて、X_iを加える」という操作を「これから袋に入れる全てのボールにつてX_iを引く」と言い換える。
また、操作3も「取り出したボールに書かれている数を記録する」という操作を「取り出したボールにそれまで引いた数を加算した数を記録する」と言い換える。
後は操作3の時に袋内の最小値を求めればおk。
毎度最小値を求めると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])

参考

https://atcoder.jp/contests/abc212/editorial/2357
https://atcoder.jp/contests/abc212/submissions/24635987

Discussion

ログインするとコメントできます