AtCoder Beginner Contest 405（Promotion of AtCoder Career Design DAY）の解説記事です。
目次
ABC405 A – Not Found
問題
問題文の要約は以下の通りです。
問題の要約
ARC Div. 1 では レーティング が \(1600\) 以上 \(2999\) 以下の人が、ARC Div. 2 ではレーティングが \(1200\) 以上 \(2399\) 以下の人がそれぞれRated 対象となる。レーティングが \(R\)の人は ARC Div. \(X\) において Rated 対象か判定せよ。
解説
if文で条件分岐を行う。
解説
入力を受け取ります。
# 入力
R,X=map(int,input().split())Rated 対象かif文で条件分岐を行います。pythonでは\(1600\) 以上 \(2999\) 以下は1600<=R<=2999のように書くことができます。
# Rated 対象か場合分け
if X==1 and 1600<=R<=2999:
print('Yes')
elif X==2 and 1200<=R<=2399:
print('Yes')
else:
print('No')解答
# 入力
R,X=map(int,input().split())
# Rated 対象か場合分け
if X==1 and 1600<=R<=2999:
print('Yes')
elif X==2 and 1200<=R<=2399:
print('Yes')
else:
print('No')ABC405 B – Not All
問題
解説
\(A\) の末尾を順に削除して \(1\) から \(M\) まですべて含まれているか判定する。
解答
# 入力
N,M=map(int,input().split())
A=list(map(int,input().split()))
# Aの末尾を順に削除して1~Mまですべて含まれているか判定
for i in range(N,-1,-1):
flag=False
for j in range(1,M+1):
if j not in A[:i]:
flag=True
if flag:
print(N-i)
exit()ABC405 C – Sum of Product
問題
解説
合計をあらかじめ計算して和を求める。
解答
# 入力
N=int(input())
A=list(map(int,input().split()))
# 答え
ans=0
# 合計
sumA=sum(A)
# 和を計算
for a in A:
sumA-=a
ans+=a*sumA
# 答えを出力
print(ans)ABC405 D – Escape Route
問題
解説
幅優先探索（BFS）を行う。
解答
from collections import deque
# 入力
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
# キューを初期化
Q = deque()
# まず、'E'（スタート地点）をすべてキューに追加
for i in range(H):
for j in range(W):
if S[i][j] == 'E':
Q.append((i, j))
# 下、右、上、左への移動
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
A = ['^', '<', 'v', '>']
# 範囲チェック
def in_bounds(i, j):
return 0 <= i < H and 0 <= j < W
# 幅優先探索（BFS）
while Q:
# キューから取り出し
i, j = Q.popleft()
# 4方向に探索
for k in range(4):
ni = i + dx[k]
nj = j + dy[k]
# 範囲外はスキップ
if not in_bounds(ni, nj):
continue
# 空きマスでないならスキップ
if S[ni][nj] != '.':
continue
# 移動方向に対応した記号を記入
S[ni][nj] = A[k]
# 新しい位置をキューに追加
Q.append((ni, nj))
# 結果を出力
for row in S:
print(''.join(row))
ABC405 E – Fruit Lineup
問題
解説
階乗、逆元をあらかじめ求め、組み合わせを計算する。
解答
MOD = 998244353
# 前計算：階乗とその逆元（mod用）
MAX = 4000000
f = [1] * (MAX + 1)
invf = [1] * (MAX + 1)
# 階乗
for i in range(1, MAX + 1):
f[i] = f[i-1] * i % MOD
# 逆元の階乗（フェルマーの小定理）
invf[MAX] = pow(f[MAX], MOD-2, MOD)
for i in range(MAX, 0, -1):
invf[i-1] = invf[i] * i % MOD
# 組み合わせの関数
def c(n, k):
if k < 0 or k > n:
return 0
return f[n] * invf[k] % MOD * invf[n - k] % MOD
# 制約を満たす並びの数を求める
A, B, C, D = map(int, input().split())
# 計算
ans = 0
for i in range(C + 1):
# 🍎🍊🍌(i個)の並べ方
left = c(A + B + i, B)
# 🍌(残り)と🍇の並べ方
right = c(D - 1 + C - i, D - 1)
ans = (ans + left * right) % MOD
# 答えを出力
print(ans)