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

A問題

マリオをイメージして条件分岐するか。
というか、stage が最後かどうかだけ見て、エラーハンドリングしなくてよくね？（）（）（）

A.py

"""
<方針>
- マリオをイメージして条件分岐するか。
- というか、`stage` が最後かどうかだけ見て、エラーハンドリングしなくてよくね？（）（）（）
"""
# 入力
S = input()

# 情報抽出
world = int(S[0])
stage = int(S[2])

# 次のステージへ
if(stage == 8):
  stage = 1
  world += 1
else:
  stage += 1

# 出力
print(str(world) + "-" + str(stage))

B問題

虱潰しで行くか。

B.py

"""
<方針>
- 虱潰しで行くか。
"""
# 入力
H, W = map(int, input().split())
SS = [input() for _ in range(H)]

# 全部2or4個の黒と隣接しているかどうか
ok = True

# 虱潰し
for i in range(H):
  for j in range(W):
    # 自分が黒の場合
    if(SS[i][j] == "#"):
      # 黒と隣接した数をカウント
      cnt = 0
      # 上下左右
      for dy, dx in [
        (+1, 0),
        (-1, 0),
        (0, +1),
        (0, -1),
        ]:
          # 上下左右を取得
          k = i + dy
          l = j + dx
          # 範囲内かどうか
          if(
            (0 <= k < H) and
            (0 <= l < W)
            ):
              # 黒かどうか
              if(SS[k][l] == "#"):
                cnt += 1
      
      # 隣接した黒の個数が2個か4個じゃない場合
      if(cnt not in [2, 4]):
        ok = False
        break

# 出力
print("Yes" if ok else "No")

C問題

方針

テストケースの線形時間でちょうどくらいで、文字の個数は線形すら許されない。
となると、各テストケースを数学的に定数時間で求める必要がある。
- まず、"A" と "C" の個数が第１のボトルネックになる。
- あと、第２のボトルネックとして、文字を全て使えたとしても、コンテスト一回あたり文字を３つ消費するため、開催できるコンテストは文字の個数の三分の一になる。
全体として、O(T) になる。

前提

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

C.py

"""
<方針>
- テストケースの線形時間でちょうどくらいで、文字の個数は線形すら許されない。
- となると、各テストケースを数学的に定数時間で求める必要がある。
  - まず、`"A"` と `"C"` の個数が第１のボトルネックになる。
  - あと、第２のボトルネックとして、。
- 全体として、`O(T)` になる。
"""
T = int(input())
for _ in range(T):
  # テストケース
  nA, nB, nC = map(int, input().split())
  
  # 第１のボトルネック
  neck1 = min(nA, nC)
  
  # 第２のボトルネック
  neck2 = (nA+nB+nC)//3
  
  # コンテスト開催可能回数
  ans = min(neck1, neck2)
  
  # 出力
  print(ans)

補足

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

今回のコンテスト

筆者について

その他

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

最後に一言

友人（@t38miwa）も復習記事を書き始めました！！
今週も忙しいので、Dはスキップします...