[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として，BFSorDFSで連結のノードの値を決めていく． - 連結でないかどうかを全て調べて同じことをしていけばいける．
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)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- ratedで参加しようか．．どうしようか．．