[ABC377] ABC 377(Atcoder Beginner Contest)のA~C(A,B,C)問題をPythonで解説(復習)

A問題

文字を一つずつ見て， A B C が全て存在していれば，並び替えれば ABC になると言える．

A.py

"""
<方針>
- 文字を一つずつ見て， `A` `B` `C` が全て存在していれば，並び替えれば `ABC` になると言える．
"""
# 入力
S = input()

# それぞれの文字が存在したかを記録するフラグ
a_exist = False
b_exist = False
c_exist = False

# 全ての文字を見る
for s in S:
  # Aだった
  if s == "A":
    a_exist = True
  # Bだった
  if s == "B":
    b_exist = True
  # Cだった
  if s == "C":
    c_exist = True

# 全部存在してたら
if a_exist and b_exist and c_exist:
  # 並び替えてABCになる
  print("Yes")
# そうでなければ
else:
  # 不可能
  print("No")

B問題

どこにコマを置くことができるかの変数 ok を作る．最初は True のリストで初期化しておく．
入力を受け取り，ルーク # があったら，それが移動できる場所を ok 上で False にする．
最後まで残った ok 上の True をカウントすればいける．

B.py

"""
<方針>
- どこにコマを置くことができるかの変数 `ok` を作る．最初は `True` のリストで初期化しておく．
- 入力を受け取り，ルーク `#` があったら，それが移動できる場所を `ok` 上で `False` にする．
- 最後まで残った `ok` 上の `True` をカウントすればいける．
"""
# 盤面の大きさ
N = 8
# 駒がおける場所
ok = [[True]*N for i in range(N)]

# 入力を受け取る
for i in range(N):
  # 入力
  S = input()
  for j, s in enumerate(S):
    # ルークがあったとき
    if s == "#":
      # 横方向の更新
      for ind in range(N):
        ok[i][ind] = False
      # 縦方向の更新
      for ind in range(N):
        ok[ind][j] = False

# おける場所をカウント
ans = 0
for i in range(N):
  for j in range(N):
    if ok[i][j]:
      ans += 1

# 出力
print(ans)

C問題

方針

B問題と同じように盤面を作るところから始めると， N がデカすぎるため， O(N^2) はとても間に合わない．
盤面は作らずとも，ナイトの可動域を登録すれば十分である．
重複の無いように，全てのナイトの可動域を登録すれば良い．
set を使うと，重複の無い追加が O(1) でできる．
高々 M 個のクイーンで前述の処理をするので， O(M) により間に合う．
テクニック
- 0-indexed でやる
- ナイトの可動域はリストを作成して， for でまとめてやる
- set の値は int にするため，縦横のいずれかの値を N 倍すると上手くいく．

前提

C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう．
AとB問題では，基本的に制約条件を見ずにやっても解ける．
しかし，C問題以降では，制約条件を見ないと必ずTLEすると思っても良い．
詳しい話は私の352回の記事のC問題の解説に記したので，是非参照してほしい．

C.py

"""
<方針>
- B問題と同じように盤面を作るところから始めると， `N` がデカすぎるため， `O(N^2)` はとても間に合わない．
- 盤面は作らずとも，ナイトの可動域を登録すれば十分である．
- 重複の無いように，全てのナイトの可動域を登録すれば良い．
- `set` を使うと，重複の無い追加が `O(1)` でできる．
- 高々 `M` 個のクイーンで前述の処理をするので， `O(M)` により間に合う．
- テクニック
  - `0-indexed` でやる
  - ナイトの可動域はリストを作成して， `for` でまとめてやる
  - `set` の値は `int` にするため，縦横のいずれかの値を `N` 倍すると上手くいく．
"""
# 入力
N, M = map(int, input().split())

# ナイトの可動域
se = set()

# 全てのナイトを処理する
for i in range(M):
  # 入力
  a, b = map(int, input().split())
  # 0-indexed
  a, b = a-1, b-1
  # ナイトの可動域を全て確認する
  for x, y in [
    (0, 0),
    (1, 2), 
    (1, -2), 
    (-1, 2), 
    (-1, -2), 
    (2, 1), 
    (2, -1), 
    (-2, 1),
    (-2, -1), 
    ]:
      # ナイトの移動先
      A = a + x
      B = b + y
      # ナイトの移動先が盤面の中のとき
      if(0<=A<N and 0<=B<N):
        # 縦方向の値をN倍したものをナイトの可動域に追加する．(setへの追加なので，重複の無い追加)
        se.add(A*N + B)
# 盤面の全体の広さから，ナイトの可動域を引くと答え．(len(se)はO(M)の処理)
print(N**2 - len(se))

補足

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

今回のコンテスト

筆者について

その他

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

最後に一言

時間ない ABCのみ　復習を