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

A問題

A.py

"""
<方針>
- ライブラリの円周率を使おう．
"""
# ライブラリ
import math

# 入力
D = int(input())

# 計算
ans = math.pi * (D/2)**2

# 出力
print(ans)

B問題

• チョコレートの縦と横の長さを管理し続ければ良い．

B.py

"""
<方針>
- チョコレートの縦と横の長さを管理し続ければ良い．
"""
# 入力
H, W, Q = map(int, input().split())
for _ in range(Q):
  match list(map(int, input().split())):
    # 分岐
    case [1, R]:
      # チョコの大きさ
      print(W*R)
      # チョコを減らす
      H -= R
    case [2, C]:
      print(H*C)
      W -= C

C問題

方針

• 愚直に全部比較すると，O(N^2) になる．
• 文字列 a だけに注目し，左から順番にシャクトリムシのように解いてみよう．
• あとはそれをアルファベット分26種類試すだけで，全体 O(N) となる．

前提

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

C.py

"""
<方針>
- 愚直に全部比較すると，`O(N^2)` になる．
- 文字列 `a` だけに注目し，左から順番にシャクトリムシのように解いてみよう．
- あとはそれをアルファベット分26種類試すだけで，全体 `O(N)` となる．
"""
N, L, R = map(int, input().split())
S = list(input()) + ["_"]*(N-L+R) # 番兵

ans = 0
for a in [chr(ord("a") + i) for i in range(26)]:
  # L~Rに何個あるのか．
  now = S[L:R+1].count(a)
  
  # シャクトリムシ
  for i in range(N-L):
    # S[i] がaかどうか
    if(S[i] == a):
      ans += now
    # シャクトリムシの尻尾切り
    if(S[L+i] == a):
      now -= 1
    # シャクトリムシの頭伸ばし
    if(S[R+1+i] == a):
      now += 1

# 出力
print(ans)

補足

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

• 今回のコンテスト

筆者について

• Atcoderアカウント
• 今回も不参加のため，成績なし．
• 解説で示したA問題の提出
• 解説で示したB問題の提出
• 解説で示したC問題の提出

その他

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

最後に一言

• 学会侍