ABC403 の振り返り(A~D, Python)

A

sum(a for i, a in enumerate(A) if i % 2 == 0)
インデックスは0から始まるので奇偶が反転する

def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    res = solve(N, A)
    print(res)


def solve(N: int, A: list[int]) -> int:
    return sum(a for i, a in enumerate(A) if i % 2 == 0)


if __name__ == "__main__":
    main()

B

あり得る場所を全探索

def main():
    T = input()
    U = input()
    res = solve(T, U)
    print("Yes" if res else "No")


def solve(T: str, U: str) -> bool:
    for i in range(len(T) - len(U) + 1):
        for j, u in enumerate(U):
            if T[i + j] != "?" and T[i + j] != u:
                break
        else:
            return True
    return False


if __name__ == "__main__":
    main()

C

基本は各ユーザーについて権限のあるページをsetで管理
すべてのページの閲覧権限を付与するときは全ページをsetに追加するのは非効率なので、任意の値を使う（本番の実装ではNoneにした）

def main():
    N, M, Q = map(int, input().split())
    queries = [list(map(int, input().split())) for _ in range(Q)]
    res = solve(N, M, Q, queries)
    for r in res:
        print("Yes" if r else "No")


def solve(N: int, M: int, Q: int, queries: list[list[int]]) -> list[bool]:
    mem: list[set[int] | None] = [set() for _ in range(N)]
    res = []
    for t, *query in queries:
        if t == 1:
            X, Y = query
            m = mem[X - 1]
            if m is not None:
                m.add(Y - 1)
        elif t == 2:
            (X,) = query
            mem[X - 1] = None
        elif t == 3:
            X, Y = query
            m = mem[X - 1]
            res.append(m is None or Y - 1 in m)
    return res


if __name__ == "__main__":
    main()

D

$D=0$ $D = 0$ のときは、 $A$ $A$ から重複削除したものが $B$ $B$ なので、 N - len(set(A))
- はじめこれを見落として、無限ループをした
- 以下は、 $D\neq 0$ の場合
順序に意味はないので各値をカウントして、 $\text{cnt}(a)=(Aに含まれるaの個数)$ $cnt (a) = (A に含まれる a の個数)$ とする
- $A$ に同じ値が複数含まれるとき、1つでも残すなら全て残しても問題ない
- →削除するかどうかは値ごとに考える
- 以下では記号 $A$ を重複を削除した集合としても用いる
任意の $a(\in \{a|a\in A, a-D \notin A\})$ $a (\in {a ∣ a \in A, a - D \in / A})$ について $\{a,a+D,a+2D,\dots\}$ ${a, a + D, a + 2 D, \dots}$ をひとまとめにして削除する値を考える
- それぞれのまとまりの削除する値は他のまとまりの削除する値に影響を与えないし、その影響を受けない
- →まとまりごとに独立に考える
(実験)
1. $a$ を残すとき削除するのは $0$ 個、 $a$ を削除するとき削除するのは $\text{cnt}(a)$ 個
2. $a+D$ を残すとき削除するのは $\text{cnt}(a)$ 個（ $a$ を残せないため）、 $a+D$ を削除するとき削除するのは $\min(0,\text{cnt}(a))+\text{cnt}(a+D)$ （ $a$ についてはどっちでもいいので小さい方）
3. もう少し繰り返すと DP（動的計画法） で解けそうなことに気づいた
DP
- dp[b][is_delete]=(要素bまで見て、要素bを削除するかがis_deleteのときの削除する最小個数) と定義する
- 初期値：dp[a] = [0, cnt(a)]
- 遷移：
  - dp[b+D][0] = dp[b][1]
  - dp[b+D][1] = min(dp[b][0], dp[b][1]) + cnt(b+D)
- 求める値：min(dp[a+D+D+...][0], dp[a+D+D+...])
- この遷移は一つ前の値しか使わないので都度更新できる

def main():
    N, D = map(int, input().split())
    A = [int(a) for a in input().split()]
    res = solve(N, D, A)
    print(res)


def solve(N: int, D: int, A: list[int]) -> int:
    if D == 0:
        return N - len(set(A))
    cnt: dict[int, int] = {}
    for a in A:
        cnt[a] = cnt.get(a, 0) + 1
    mem: set[int] = set()
    res = 0
    for a in sorted(cnt):
        if a in mem:
            continue
        dp = [0, 0]
        while a in cnt:
            dp[0], dp[1] = min(dp[0], dp[1]) + cnt[a], dp[0]
            a += D
            mem.add(a)
        res += min(dp)
    return res


def solve_gu(N: int, D: int, A: list[int]) -> int:
    """デバッグ時に利用した愚直解"""
    res = N
    for i in range(1 << N):
        mem = set()
        r = 0
        for j in range(N):
            if (i >> j) & 1:
                a = A[j]
                if (a - D) in mem:
                    break
                if (a + D) in mem:
                    break
                mem.add(a)
            else:
                r += 1
        else:
            res = min(res, r)
    return res


if __name__ == "__main__":
    main()

E

全然わからなかった
- trie木勉強します