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

A問題

• for 文で取り出す。
• % を使って奇数番目を判定する。

A.py

"""
<方針>
- `for` 文で取り出す。
- `%` を使って奇数番目を判定する。
"""
# 入力
N = int(input())
A = list(map(int, input().split()))

# 答え
ans = 0
# 順番に見る
for i in range(N):
  # 奇数番目の時
  if(i%2 == 0):
    # 足す
    ans += A[i]

# 出力
print(ans)

B問題

• T の見始める index を変えていき、可能性を探る。

B.py

"""
<方針>
- `T` の見始める `index` を変えていき、可能性を探る。
"""
# 入力
T = input()
U = input()

# indexを変えてみていく。
for i in range(len(T)-len(U)+1):
  # 可能性があるかどうかのフラグ
  ok = True
  # 左からみていく
  for j in range(len(U)):
    # Tが? or TとUの文字が一致しなければ、可能性がない。
    if not ((T[i+j] == "?") or (T[i+j] == U[j])):
      ok = False
  
  # 可能性があれば
  if(ok):
    print("Yes")
    exit()

# 可能性がなければ、
print("No")

C問題

方針

• 基本的に言われた通りにシミュレーションする。
• しかし、ユーザーとアクセス先に関する二重配列を作る空間的余裕はない。O(MN) で TLE(MLE?) する。
  • そこで、片方を set にすることで対処する。
• しかし、アクセス権限を全員に与える処理を愚直にやると、O(MQ) で TLE する。
  • そこで、全ての権限を与えられたかどうかの変数も用意することで対処する。

前提

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

C.py

"""
<方針>
- 基本的に言われた通りにシミュレーションする。
- しかし、ユーザーとアクセス先に関する二重配列を作る空間的余裕はない。`O(MN)` で `TLE(MLE?)` する。
  - そこで、片方を `set` にすることで対処する。
- しかし、アクセス権限を全員に与える処理を愚直にやると、`O(MQ)` で `TLE` する。
  - そこで、全ての権限を与えられたかどうかの変数も用意することで対処する。
"""
N, M, Q = map(int, input().split())
# XがYにアクセスできるかどうか
access = [set() for _ in range(N+1)]
# Xが全てにアクセスできるかどうか
full_access = [False]*(N+1)

for _ in range(Q):
  match list(map(int, input().split())):
    case [1, X, Y]:
      # XにYへのアクセス許可
      access[X].add(Y)
    case [2, X]:
      # Xにフルアクセス許可
      full_access[X] = True
    case [3, X, Y]:
      # XがYへアクセスできる or フルアクセスがある
      print("Yes" if ((Y in access[X]) or full_access[X]) else "No")

D問題

• B にそれぞれの数字が何回出現したかを記録する。
• D == 0 の時は、
  • 重複してる分だけが答え。
• D != 0 の時は、
  • C に D 間隔のものを登録する。
  • C のそれぞれの要素のどれを 0 にすれば良いのか dp で求める。

D.py

"""
<方針>
- `B` にそれぞれの数字が何回出現したかを記録する。
- `D == 0` の時は、
  - 重複してる分だけが答え。
- `D != 0` の時は、
  - `C` に `D` 間隔のものを登録する。
  - `C` のそれぞれの要素のどれを `0` にすれば良いのか `dp` で求める。
"""
N, D = map(int, input().split())
A = list(map(int, input().split()))

INF = float("inf")

# Bの構築
B = [0]*(max(A)+1)
for a in A:
  B[a] += 1

if(D == 0):
  # D==0の時は、重複だけをチェック
  print(sum([max(0, b-1) for b in B]))
else:
  # D!=0の時は、D間隔のところずつ考える
  ans = 0
  # indexをずらしてそれぞれの間隔を見る
  for i in range(D):
    # D間隔で要素を取り出す。
    C = []
    for j in range(i, len(B), D):
      C.append(B[j])
    
    # dpで解く
    ## dp[i+1][0] := i番目の要素を取り除いたときの最適値
    ## dp[i+1][1] := i番目の要素を残したときの最適値
    dp = [[INF, INF] for _ in range(len(C)+1)]
    # 初期値
    dp[0] = [0, 0]
    for i in range(len(C)):
      # すでに値が存在しない時、
      if(C[i] == 0):
        # 直前と同じ
        dp[i+1][0] = dp[i+1][1] = min(dp[i])
      # 値が存在する時、
      else:
        # 取り除く時は、直前の値にC[i]を足す
        dp[i+1][0] = min(dp[i][0], dp[i][1]) + C[i]
        # 取り除かない時は、直前に値が無いパターンからの遷移しかない。
        dp[i+1][1] = dp[i][0]
    
    # 答えに追加
    ans += min(dp[-1])
  
  print(ans)

補足

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

• 今回のコンテスト

筆者について

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

その他

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

最後に一言

• 筋トレします。
• D 問題の DP 自分で思いついたの成長を感じる。