ABC403をPythonで（A～D）

AtCoder Beginner Contest 403（Promotion of AtCoder Career Design DAY）の解答等の速報的まとめ

A問題

最初から1つおきに選択した総和を出力

A

n = int(input())
a = list(map(int, input().split()))
print(sum(a_i for a_i in a[::2]))

B問題

全パターンをシミュレーションする

B

t = input()
u = input()

for i in range(len(t) - len(u) + 1):
    flag = True
    for t_i, u_i in zip(t[i:], u):
        if t_i != "?" and t_i != u_i:
            flag = False
    if flag:
        exit(print("Yes"))

print("No")

C問題

前ページ見れる人と各人が見れるページ一覧をsetで管理する

C

n, m, q = map(int, input().split())

all_view = set()
can_view = [set() for _ in range(n + 1)]

for _ in range(q):
    com = list(map(int, input().split()))
    if com[0] == 1:
        x, y = com[1:]
        can_view[x].add(y)
    elif com[0] == 2:
        x = com[1]
        all_view.add(x)
    elif com[0] == 3:
        x, y = com[1:]
        if x in all_view or y in can_view[x]:
            print("Yes")
        else:
            print("No")

D問題

$d=0$のとき、同じ数は１つを残して消す

$d > 0$のときは、$d$の余りで各数をグループ分けができ、各グループの中で連続して数が出現する区間でのみどこを消すか考慮する必要が出てくる
消す個数はDPで最小パターンを考える

D

from collections import Counter

def solve(lst):
    # dp[i][j] = i番目でj(0消した、１消さない)のときの消した最小個数
    dp = [[0] * 2 for _ in range(len(lst))]
    for i, l_i in enumerate(lst):
        # 消す
        if i == 0:
            dp[i][0] = l_i
        else:
            dp[i][0] = min(dp[i - 1]) + l_i
        # 消さない
        if i > 0:
            dp[i][1] = dp[i - 1][0]
    return min(dp[-1])


n, d = map(int, input().split())
a = list(map(int, input().split()))

count = Counter(a)

ans = 0
if d == 0:
    for c_i in count.values():
        ans += max(c_i - 1, 0)
else:
    groups = [list() for _ in range(d)]

    for i in range(max(a) + 1):
        g_i = i % d
        if i in count:
            groups[g_i].append(count[i])
        else:
            if groups[g_i]:
                ans += solve(groups[g_i])
                groups[g_i] = list()

    for g_i in groups:
        if g_i:
            ans += solve(g_i)

print(ans)

E問題

• 感想
  文字列を木に落とし込む方法があったのは覚えていたが、それの名前ややり方を思い出せなかった
  試行錯誤したけどWAを積み重ねて終了

(追記) トライ木だった。もう忘れない