AtCoder Beginner Contest 405（Promotion of AtCoder Career Design DAY）の解答等の速報的まとめ
問題文のまま
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")
先頭から見て最初に全部揃う個所まで消すのが答え。揃う個所がないときは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)
問題文の式を変形すると
$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
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="")
まず$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)
Views: 0
