ABC405をPythonで（A～E）

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

A問題

問題文のまま

A

r, x = map(int, input().split())
print("Yes" if (x == 1 and 1600 <= r < 3000) or (x == 2 and 1200 <= r < 2400) else "No")

B問題

先頭から見て最初に全部揃う個所まで消すのが答え。揃う個所がないときは0が答え

B

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

s = set()
target = {i for i in range(1, m + 1)}
border = n
for i, a_i in enumerate(a):
    s.add(a_i)
    if s == target:
        border = i
        break

print(n - border)

C問題

問題文の式を変形すると
$a_1 \times (a_2 + a_3 + ...+ a_n) + a_2\times(a_3+a_4+...+a_n)+...$
となるので、後ろから計算していく

C

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

ans = 0
sums = 0
for a_i in a[::-1]:
    ans += a_i * sums
    sums += a_i

print(ans)

D問題

すべての非常口から始まるダイクストラの要領で来た方向に矢印を書いていく

D

from collections import deque

h, w = map(int, input().split())
a = [input() for _ in range(h)]

ans = [[""] * w for _ in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] != ".":
            ans[i][j] = a[i][j]
        if a[i][j] == "E":
            q.append([i, j])

arrays = [[1, 0, "^"], [-1, 0, "v"], [0, 1, "<"], [0, -1, ">"]]
while q:
    x, y = q.popleft()
    for a_i, a_j, arrow in arrays:
        x_i, y_i = x + a_i, y + a_j
        if 0 <= x_i < h and 0 <= y_i < w and ans[x_i][y_i] == "":
            ans[x_i][y_i] = arrow
            q.append([x_i, y_i])

for ans_i in ans:
    print(*ans_i, sep="")

E問題

まず$a$の左端を固定して調べていく。その$a$の左端までには$b$しか混ざらないので組み合わせは$a$の左端-1までに$a$を置くパターン数になる

残りのスペースには$b,c,d$を置くが、$b$と$d$は混ざらないため$c$の場所を確定させたら1通りに定まる

E

class combination:
    # nが小さく(10**7未満)ないと厳しい
    def __init__(self, N, mod):
        self.fact = [1, 1]
        self.factinv = [1, 1]
        self.inv = [0, 1]

        for i in range(2, N + 1):
            self.fact.append((self.fact[-1] * i) % mod)
            self.inv.append((-self.inv[mod % i] * (mod // i)) % mod)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % mod)

    def cmb(self, n, r):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return self.fact[n] * self.factinv[r] * self.factinv[n - r] % mod

a, b, c, d = map(int, input().split())
n = a + b + c + d
mod = 998244353

C = combination(a + b + c + d, mod)

ans = 0
for i in range(a, a + b + 1):
    # aの一番右がiにある
    c_i = C.cmb(i - 1, a - 1)
    # cの場所が決まれば、bとdの置き方は１通りに固定
    ans += c_i * C.cmb(n - i, c) % mod
    ans %= mod

print(ans)