[ABC405] ABC 405(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)
A問題
-
Xによって分岐する。 -
WYSIWYGですね（）。
A.py
"""
<方針>
- `X` によって分岐する。
- `WYSIWYG` ですね（）。
"""
# 入力
R, X = map(int, input().split())
# Div1
if(X == 1):
if(1600 <= R <= 2999):
print("Yes")
else:
print("No")
# Div2
elif(X == 2):
if(1200 <= R <= 2399):
print("Yes")
else:
print("No")
B問題
-
.pop()を使って、末尾の要素を消していく。 - 逐一全ての整数を含むかを確認する。
B.py
"""
<方針>
- `.pop()` を使って、末尾の要素を消していく。
- 逐一全ての整数を含むかを確認する。
"""
# 入力
N, M = map(int, input().split())
A = list(map(int, input().split()))
# popで要素を消していく。
for cnt in range(N+1):
# 要素が存在するかを管理
exists = [False]*(M+1)
for a in A:
exists[a] = True
# 1~Mまで全ての要素があれば、
if all(exists[1:]):
# 末尾を消す
A.pop()
# 消えていれば、終了する。
else:
break
# 出力
print(cnt)
C問題
方針
-
O(N^2)はダメそう。なんとかO(N)程度で終わらせる必要がある。 -
Aをフルメッシュに掛け合わせたものから、自分自身の２乗を引いて、半分にすれば問題なさそう。{ (a_1 + a_2 + ... + a_n)^2 - (a_1^2 + a_2^2 + ... + a_n^2) }/2
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- `O(N^2)` はダメそう。なんとか `O(N)` 程度で終わらせる必要がある。
- `A` をフルメッシュに掛け合わせたものから、自分自身の２乗を引いて、半分にすれば問題なさそう。
- `{ (a_1 + a_2 + ... + a_n)^2 - (a_1^2 + a_2^2 + ... + a_n^2) }/2`
"""
N = int(input())
A = list(map(int, input().split()))
# フルメッシュ
full_mesh = sum(A)**2
# 自分自身の２乗
sum_square = sum([a**2 for a in A])
# 答え
ans = (full_mesh - sum_square) // 2
print(ans)
D問題
-
BFSして、どのマスの方向から来たかを塗れば良さそう。
D.py
"""
<方針>
- `BFS` して、どのマスの方向から来たかを塗れば良さそう。
"""
from collections import deque
# 入力
H, W = map(int, input().split())
SS = [list(input()) for _ in range(H)]
q = deque()
# スタート地点を登録
for i in range(H):
for j in range(W):
if(SS[i][j] == "E"):
q.append([i, j])
while q:
i, j = q.popleft() # BFS
# 次をみる
for di, dj, x in [
[0, 1, ">"],
[0, -1, "<"],
[1, 0, "v"],
[-1, 0, "^"],
]:
I = i-di
J = j-dj
# 枠内
if(0<=I<H and 0<=J<W):
# まだ道が決まってない
if(SS[I][J] == "."):
# 道を決める
SS[I][J] = x
# 次を格納
q.append([I, J])
# 出力
for S in SS:
print("".join(S))
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．