😎

AtCoder ABC220 個人的メモ

4 min read

所感

入水!!
やったぜ
abc220score

A - Find Multiple

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

for i in range(1, 10 ** 3):
    if A <= C * i <= B:
        print(C * i)
        exit()

print(-1)

B - Base K

https://docs.python.org/ja/3/library/functions.html?highlight=int#int
K = int(input())
# int(x,K)でK進数の文字列xを10進数に変換できる
A, B = map(lambda x: int(x, K), input().split())

print(A * B)

C - Long Sequence

https://atcoder.jp/contests/abc220/editorial/2683
N = int(input())
A = list(map(int, input().split()))
X = int(input())

sum_A = sum(A)
multi = X // sum_A
now_sum = sum_A * multi
ans = len(A) * multi
for a in A:
    if now_sum > X:
        print(ans)
        exit()
    now_sum += a
    ans += 1

print(ans)

D - FG operation

https://atcoder.jp/contests/abc220/editorial/2682
N = int(input())
A = list(map(int, input().split()))
MOD = 998244353

# dp[i][j]:=i番目までのAiでK=jとなる場合の数
dp = [[0] * (10) for _ in range(N)]
dp[0][A[0]] = 1
for i in range(1, N):
    a = A[i]
    for j in range(10):
        dp[i][(a + j) % 10] += dp[i - 1][j]
        dp[i][(a + j) % 10] %= MOD
        dp[i][(a * j) % 10] += dp[i - 1][j]
        dp[i][(a * j) % 10] %= MOD

print(*dp[-1], sep="\n")

F - Distance Sums 2

f(i)=\sum_{j=1}^Ndis(i,j)とする。
とりあえずi=1としてf(1)=\sum_{j=1}^Ndis(1,j)を考えてみる。
これは頂点1からdfsなりbfsをすればO(N)で求められる(dfs,bfsの計算量は頂点の個数と辺の個数の和)。
これを全ての頂点から求めると全体でO(N^2)となってtleする。
なので高速化したい。

f(1)を求めた後に別の頂点でf(i)を求める時、f(1)との差分が分かれば新たにグラフの探索する必要は無いので高速化できそう。
なので下図のようにグラフで頂点iが変化したときのf(i)の変化を考えてみる。
頂点横の数字はdis(i,j)を示している。

abc220f

すると以下のことが分かる。


iが頂点aからaと隣接している頂点bへ変化した時、dis(b,j)dis(a,j)から以下のように変化する。

  • abを結ぶ辺を除いた場合に頂点jaと連結な場合(水色の丸で囲まれていない頂点)
    dis(b,j)=dis(a,j)+1
  • abを結ぶ辺を除いた場合に頂点jbと連結な場合(水色の丸で囲んだ頂点)
    dis(b,j)=dis(a,j)-1

つまり、f(b)f(a)bの部分木の大きさが分かればO(1)で求めることができる。
(bを含まないaの連結成分の大きさは、全ての頂点数をNとするとN-(bの部分木の大きさ)で求まる)

これより以下の手順で答えを求めることができる。

  1. 頂点1を根とするdfsをして各頂点の部分木の大きさを求める。O(N)
  2. f(1)=\sum_{j=1}^Ndis(1,j)を求める。O(1)
    ↑で求めた部分木の大きさから求めることができる。
  3. bfsで頂点1に隣接する頂点から順にf(i)=\sum_{j=1}^Ndis(i,j)を求める。O(N)

よって全体でO(N)となり十分高速に答えを求めることができる。

from collections import deque
from sys import setrecursionlimit

setrecursionlimit(10 ** 7)


def search_num_child(now: int):
    """0を根とした木において、頂点now以下の頂点数(頂点nowとその子の数)をdfsで求める"""
    if num_child[now]:
        return num_child[now]
    num_child[now] = 1
    for n_node in edge[now]:
        if num_child[n_node]:
            continue
        num_child[now] += search_num_child(n_node)
    return num_child[now]


N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N - 1):
    x, y = map(lambda n: int(n) - 1, input().split())
    edge[x].append(y)
    edge[y].append(x)

# num_child[i]:=頂点0を根としたiの部分木の大きさ(iを含む)
num_child = [0] * N
search_num_child(0)
dis_from_zero = sum(num_child) - N

# 0を根としてbfsで高さが低い頂点から(0に近い頂点から)ansを求めていく
ans = [dis_from_zero] * N
seen = [0] * N
queue = deque([(0, 0)])
while queue:
    now, parents = queue.popleft()
    seen[now] = 1

    if now:
        res = ans[parents]
        # 移動後の頂点の子ノードは距離が減る
        res -= num_child[now]
        # 移動後の頂点の親ノードは距離が増える
        res += N - num_child[now]
        ans[now] = res

    for n_node in edge[now]:
        if seen[n_node]:
            continue
        queue.append((n_node, now))

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

Discussion

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