[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))

補足

関係するリンク(参考文献など)

今回のコンテスト

筆者について

その他

間違いを含んでいる可能性があります．
方針と言いつつ，方針ではない感想などを書いている可能性があります．
A問題から解説がだんだん省略されます．
コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．

最後に一言

友人（@hamao）が面白いものを作ってます。よければ使ってみて。