💬

AtCoder ABC221 個人的メモ

2021/10/04に公開

Python

競技プログラミング

AtCoder

tech

A - Seismic magnitude scales

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

a = pow(32, A)
b = pow(32, B)

print(a // b)

B - typo

問題文通りにシミュレーション

S = list(input())
T = list(input())

if S == T:
    print("Yes")
    exit()

L = len(S)
for i in range(L - 1):
    lst = list(S)
    lst[i], lst[i + 1] = lst[i + 1], lst[i]
    if lst == T:
        print("Yes")
        exit()

print("No")

C - Select Mul

想定解と一緒

N = input()

# Nを2つの整数a,bに分離することを考える
# aとして使用する桁をbit全探索する
# (選んだ数の順序は最大の場合になるように大きい順に並べる)
L = len(N)
ans = 0
for bit in range(1 << L):
    a, b = [], []
    for i in range(L):
        if bit & (1 << i):
            a.append(int(N[i]))
        else:
            b.append(int(N[i]))

    # aかbとして選ばれた桁が存在しない場合は飛ばす
    if not a or not b:
        continue

    # 選ばれた桁の数字を並べ替えて最大のa,bにする
    a.sort(reverse=True)
    a = int("".join(map(str, a)))
    b.sort(reverse=True)
    b = int("".join(map(str, b)))

    ans = max(ans, a * b)

print(ans)

1日目から順にその日にログインしている人数を数えれば解は求まりそう。
しかし、制約で $A_i\leq 10^9$ となっているので最大で $10^9$ 日目まで数えることになるのでtleする。
$N$ の制約を見ると $N\leq 2\times 10^5$ とあるので、ログインしている人数に変化のある日は最大で $4\times 10^5$ 通りと分かる。
よって、ログイン人数に変化のある日のみ人数を数えてそれ以外の日は一括して数え上げれば計算量が $O(N)$ になるので間に合いそう。
というわけで以下の実装でおｋ。
本番では座標圧縮→いもす法→座標復元でacしたけど、イベントソートとか言うのもあるらしい。

いずれの実装でもソートしているので実際の計算量は $O(N\log N)$ になっている。

いもす法

from itertools import accumulate

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]

# 座標圧縮
login_logout_days = {0}
for a, b in AB:
    login_logout_days.add(a)
    login_logout_days.add(a + b)
login_logout_days = sorted(login_logout_days)
day_to_i = {v: i for i, v in enumerate(login_logout_days)}  # 圧縮
i_to_day = {i: v for i, v in enumerate(login_logout_days)}  # 復元

# imos法
cnt = [0] * (N * 2 + 1)
for a, b in AB:
    cnt[day_to_i[a]] += 1
    cnt[day_to_i[a + b]] -= 1
cumsum = list(accumulate(cnt))

ans = [0] * (N + 1)
for i in range(len(i_to_day) - 1):
    num_player = cumsum[i]
    ans[num_player] += i_to_day[i + 1] - i_to_day[i]

print(*ans[1:])

イベントソート

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]

events = [(0, 0)]
for a, b in AB:
    events.append((a, +1))
    events.append((a + b, -1))
events.sort()

ans = [0] * (N + 1)
player_cnt = 0
for i in range(1, len(events)):
    now_day , plus_one = events[i]
    last_day, _        = events[i - 1]

    ans[player_cnt] += now_day - last_day
    player_cnt += plus_one

print(*ans[1:])

参考

ABC128Eの公式解説

F - Diameter set

from collections import deque


def bfs(start: int):
    """
    頂点startを根として各頂点の深さを求めつつbfsをする
    帰り値はD=最大深度、i=最大深度の頂点1つの頂点番号
    """
    depth_from_node[start] = 0
    D = 0
    i = start
    queue = deque([start])
    while queue:
        now = queue.popleft()
        for n_node in edge[now]:
            if depth_from_node[n_node] != -1:
                continue
            queue.append(n_node)
            depth_from_node[n_node] = depth_from_node[now] + 1
            parent[n_node] = now
            if depth_from_node[now] + 1 > D:
                D = depth_from_node[now] + 1
                i = n_node
    return D, i


def M_cnt_func(start: int, target_depth: int):
    """
    頂点startを根としてbfsをする
    深度がtarget_depthと一致する頂点の数を数えて返す
    """
    res = 0
    height[start] = 0
    queue = deque([start])
    while queue:
        now = queue.popleft()
        if height[now] == target_depth:
            res += 1
        for n_node in edge[now]:
            if height[n_node] != -1:
                continue
            queue.append(n_node)
            height[n_node] = height[now] + 1
    return res


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

# 適当な頂点を根として木の探索
# → 根から一番遠かった頂点を根としてもう一度木の探索
# → その時の最大深度が木の直径D
depth_from_node = [-1] * N
parent = [-1] * N
_, i = bfs(0)
depth_from_node = [-1] * N
parent = [-1] * N
D, now = bfs(i)
# 2点間の距離が木の直径Dと等しくなる場合の経路routeを木探索から復元
route = [now]
while now != i:
    now = parent[now]
    route.append(now)

# Dが奇数の場合
if D % 2:
    # 辺a-bを削除
    a, b = route[D // 2: D // 2 + 2]
    edge[a].discard(b)
    edge[b].discard(a)

    ans = 1
    height = [-1] * N
    for i in (a, b):
        ans *= M_cnt_func(i, (D - 1) // 2)
        ans %= MOD
# Dが偶数の場合
else:
    # 頂点Cを端点とする辺を削除
    C = route[D // 2]
    pnts = set(edge[C])
    for i in pnts:
        edge[i].discard(C)
    edge[C] = set()

    ans = 1
    M_cnt = 0
    height = [-1] * N
    for i in pnts:
        res = M_cnt_func(i, D // 2 - 1)
        M_cnt += res
        ans *= res + 1
        ans %= MOD
    ans -= M_cnt + 1
    ans %= MOD

print(ans)