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

https://atcoder.jp/contests/abc405

A

• 条件分岐して不等号で挟む
• 辞書を使うと楽

def main():
    R, X = map(int, input().split())
    res = solve(R, X)
    print("Yes" if res else "No")


rated_range = {1: (1600, 2999), 2: (1200, 2399)}


def solve(R: int, X: int) -> bool:
    left, right = rated_range[X]
    return left <= R <= right


if __name__ == "__main__":
    main()

B

• 空の整数列に $A$ の先頭の値から順番に追加することを考える
• 初めて $1$ 以上 $M$ 以下の整数がすべて含まれるようになる位置を求める
• $A$ を後ろから見たとき、求めた位置の値を削除しないとすべて含まれてしまう。かつ、求めた位置の値を削除すればすべて含まれることはない
• よって、求めた位置を削除するための個数を求める

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


def solve(N: int, M: int, A: list[int]) -> int:
    mem: set[int] = set()
    for i, a in enumerate(A):
        mem.add(a)
        if len(mem) >= M:
            return N - i
    return 0


if __name__ == "__main__":
    main()

C

• 2つの値の積の和なので $(A_1+A_2+\cdots+A_N)^2$ を考えた

  $$\begin{aligned} \sum_{1\leq i\leq j\leq N}A_iA_j&=(A_1+A_2+\cdots+A_N)^2\\&=A_1A_1+A_1A_2+\cdots+A_1A_N+\cdots+A_NA_1+A_NA_2+\cdots+A_NA_N\\&=(A_1^2+A_2^2+\cdots+A_N^2)+(2A_1A_2+\cdots+2A_1A_N+2A_2A_3+\cdots+2A_{N-1}A_N)\\&=\sum_{1\leq i\leq N}A_i^2+2\sum_{1\leq i\leq j\leq N}A_iA_j \end{aligned}$$

• 以上より

  $$\sum_{1\leq i\leq j\leq N}A_iA_j=\frac{\left(\sum_{1\leq i\leq N}A_i\right)^2-\sum_{1\leq i\leq N}A_i^2}{2}$$

• 2乗を $O(1)$ で求められるとき、 $\left(\sum_{1\leq i\leq N}A_i\right)^2$ も $\sum_{1\leq i\leq N}A_i^2$ も $O(N)$ で求められる

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:
    sum_A = sum(A)
    square_sum_A = sum(a * a for a in A)
    return (sum_A * sum_A - square_sum_A) // 2


if __name__ == "__main__":
    main()

D

• 出口を始点として BFS（幅優先探索）
• 始点が複数あるだけでよくあるBFS

from collections import deque


def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    res = solve(H, W, S)
    for r in res:
        print("".join(r))


def solve(H: int, W: int, S: list[list[str]]) -> list[list[str]]:
    T = [[S[i][j] for j in range(W)] for i in range(H)]
    que: deque[tuple[int, int]] = deque()

    for i in range(H):
        for j in range(W):
            if T[i][j] == "E":
                que.append((i, j))

    directions = {(-1, 0, "v"), (1, 0, "^"), (0, -1, ">"), (0, 1, "<")}

    def is_in(i, j):
        return 0 <= i < H and 0 <= j < W

    while que:
        i, j = que.popleft()
        for di, dj, t in directions:
            ni, nj = i + di, j + dj
            if is_in(ni, nj) and T[ni][nj] == ".":
                T[ni][nj] = t
                que.append((ni, nj))
    return T


if __name__ == "__main__":
    main()