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

A問題

12 回ループを回せば良い．
ループの回数と，そのとき入力された文字数が等しい時，答え ans をインクリメントすれば良い．

A.py

"""
<方針>
- `12` 回ループを回せば良い．
- ループの回数と，そのとき入力された文字数が等しい時，答え `ans` をインクリメントすれば良い．
"""
# 答え
ans = 0
# 12回ループ
for i in range(12):
  # 入力文字列
  s = input()
  # 入力文字列がループの回数と等しい時，
  if(len(s) == (i+1)): # 0-indexedなので，+1する．
    # 答えをインクリメントする
    ans += 1
# 出力
print(ans)

B問題

移動する 26 - 1 = 25 回分シミュレーションすれば，最小の移動回数 ans が求まる．
移動元 src と移動先 dst を int で持つ．
アルファベットは ord() を利用することで，上手く数字で扱っていく．

B.py

"""
<方針>
- 移動する `26 - 1 = 25` 回分シミュレーションすれば，最小の移動回数 `ans` が求まる．
- 移動元 `src` と移動先 `dst` を `int` で持つ．
- アルファベットは `ord()` を利用することで，上手く数字で扱っていく．
"""
# 入力
S = input()

# 最小の移動回数
ans = 0
# 25回分の移動シミュレーション
for i in range(25):
  # 移動元/移動先の位置を計算する．
  for j in range(26):
    # 移動元の位置
    if(ord(S[j]) == ord("A") + i):
      src = j
    # 移動先の位置
    if(ord(S[j]) == ord("A") + i+1):
      dst = j
  # 移動回数を更新
  ans += abs(src-dst)
# 出力
print(ans)

C問題

方針

当然だが，全パターンを調べていたら， O(N^2) かかって TLE する．
普通に A と B の最大値を足せば良くね？

前提

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

C.py

"""
<方針>
- 当然だが，全パターンを調べていたら， `O(N^2)` かかって `TLE` する．
- 普通に `A` と `B` の最大値を足せば良くね？
"""
# 入力
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# 出力
print(max(A) + max(B))

D問題

それぞれのノードとノードの重みを双方向から記録しておく．
最初の値を適当に 0 として， BFS or DFS で連結のノードの値を決めていく．
連結でないかどうかを全て調べて同じことをしていけばいける．

D.py

"""
<方針>
- それぞれのノードとノードの重みを双方向から記録しておく．
- 最初の値を適当に `0` として， `BFS` or `DFS` で連結のノードの値を決めていく．
- 連結でないかどうかを全て調べて同じことをしていけばいける．
"""
from collections import deque
# 入力
N, M = map(int, input().split())
E = [[] for _ in range(N)]
for i in range(M):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1
  
  # 双方向でエッジを構築
  E[u].append([v, w])
  E[v].append([u, -w])

# 答え
ans = [None]*N

# 全てのノードを見ていく．
for i in range(N):
  # 値が決定していれば，探索しなくて良い．
  if(ans[i] is not None):
    continue
  
  q = deque() # 非再帰DFS
  
  # [ノードのインデックス, 値]
  q.append([i, 0])
  
  # 再帰
  while q:
    # x: ノード
    # b: 値
    x, b = q.popleft()
    
    # ノードの値を決定
    ans[x] = b
    
    # 接続しているノードを見る
    for v, w in E[x]:
      # 値が決定していなければ
      if(ans[v] is None):
        # 探索対象にする．
        q.append([v, b+w])
# 出力
print(*ans)

補足

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

今回のコンテスト

筆者について

その他

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

最後に一言

ratedで参加しようか．．どうしようか．．