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

A問題

• 「時」が前であるかをチェックする。
• 「時」が同じなら、「分」をチェックする。

A.py

"""
<方針>
- 「時」が前であるかをチェックする。
- 「時」が同じなら、「分」をチェックする。
"""
# 入力
A, B, C, D = map(int, input().split())

# 時が前なら
if(A > C):
  print("Yes")
# 時が同じで、分が前なら
elif(A == C and B > D):
  print("Yes")
# それ以外
else:
  print("No")

B問題

• for で順番にかけていき、K+1 桁以上になったら、1 に戻す。

B.py

"""
<方針>
- `for` で順番にかけていき、`K+1` 桁以上になったら、`1` に戻す。
"""
# 入力
N, K = map(int, input().split())
A = list(map(int, input().split()))

# 答え
ans = 1
# 順番に見る
for a in A:
  # かける
  ans *= a
  # 桁数がKを超えた時、
  if(len(str(ans)) > K):
    ans = 1

# 出力
print(ans)

C問題

方針

• 全ての連続部分列を作成すると、O(N^2) かかり、とても間に合わない。
• なんとか線形時間で処理を組む必要がある。
• まず、R に、どの位置で、^ or v になるかを見つける。 O(N)
• 次に、R を見て、^ の次に v が来る場所を見つける。O(N)
• そのとき、^ の一個前のやつとの距離を l とし、 v の一個次のやつとの距離を r とし、l*r を答えに追加する。O(1)
• よって、全体では、O(N+N*1) = O(N) 程度で処理できた。

前提

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

C.py

"""
<方針>
- 全ての連続部分列を作成すると、`O(N^2)` かかり、とても間に合わない。
- なんとか線形時間で処理を組む必要がある。
- まず、`R` に、どの位置で、`^` or `v` になるかを見つける。 `O(N)`
- 次に、`R` を見て、`^` の次に `v` が来る場所を見つける。`O(N)`
- そのとき、`^` の一個前のやつとの距離を `l` とし、 `v` の一個次のやつとの距離を `r` とし、`l*r` を答えに追加する。`O(1)`
- よって、全体では、`O(N+N*1) = O(N)` 程度で処理できた。
"""
# 入力
N = int(input())
P = list(map(int, input().split()))

# ^とvを格納する。
## ^: [1, index]
## v: [-1, index]
R = []

R.append([0, 0]) # 番兵

# ラスター走査
for i in range(1, N-1):
  # ^ の時、
  if(P[i-1] < P[i] > P[i+1]):
    R.append([1, i])
  # v の時、
  if(P[i-1] > P[i] < P[i+1]):
    R.append([-1, i])

R.append([0, N-1]) # 番兵

# 答えを集計する。
ans = 0
for i in range(1, len(R)-1):
  # ^の次vがきてる時、
  if(R[i][0] == 1 and R[i+1][0] == -1):
    # 左の長さ
    l = R[i][1] - R[i-1][1]
    # 右の長さ
    r = R[i+2][1] - R[i+1][1]
    # 答えに追記
    ans += (l*r)

# 出力
print(ans)

D問題

• H x W の空間はリストで持てないから、集合で管理する。
• X で処理したら、Y も更新する。逆も然り。

D.py

"""
<方針>
- `H x W` の空間はリストで持てないから、集合で管理する。
- `X` で処理したら、`Y` も更新する。逆も然り。
"""
from collections import defaultdict

_, _, N = map(int, input().split())

# X[x][y] -> (x, y) にゴミがある。
X = defaultdict(set)
# Y[y][x] -> (x, y) にゴミがある。
Y = defaultdict(set)

# X, Yの作成
for _ in range(N):
  x, y = map(int, input().split())
  Y[y].add(x)
  X[x].add(y)

# ループ処理
for _ in range(int(input())):
  match list(map(int, input().split())):
    case [1, x]:
      # xにあるゴミを出力
      print(len(X[x]))
      # Yの方のゴミを消す
      for y in X[x]:
        Y[y].discard(x)
      # Xの方のゴミを消す
      X[x] = set()
    # 上と同じ
    case [2, y]:
      print(len(Y[y]))
      for x in Y[y]:
        X[x].discard(y)
      Y[y] = set()

補足

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

• 今回のコンテスト

筆者について

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

その他

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

最後に一言

• 奇妙な記事があるな...