[ABC421] ABC 421(Atcoder Beginner Contest)のA~C(A,B,C)問題をPythonで解説(復習)
A問題
- 配列で管理する。
- 添字を元に照合をを行う。
A.py
"""
<方針>
- 配列で管理する。
- 添字を元に照合をを行う。
"""
# 入力
N = int(input())
S = [input() for _ in range(N)]
X, Y = input().split()
# 添字を取得
index = int(X) - 1
# 宛先が正しいかの確認
if(S[index] == Y):
print("Yes")
else:
print("No")
B問題
- 関数を定義する。
- ループ処理を施して、
a_10を手に入れる。
B.py
"""
<方針>
- 関数を定義する。
- ループ処理を施して、`a_10` を手に入れる。
"""
# 入力
X, Y = map(int, input().split())
# a2, a1を受け取って、a3, a2を返す。
def a(a2:int, a1:int)->(int, int):
# 足す
a3 = (a2+a1)
# 反転させる
a3 = str(a3)[::-1]
# 数字にする
a3 = int(a3)
return a3, a2
# ループ処理
for _ in range(8):
Y, X = a(Y, X)
# 出力
print(Y)
C問題
方針
- なんとか、最終形が
ABAB...ABABorBABA...BABAであることを見抜く。 - その形にするために、一つ一つの文字
O(N)を具体的に動かしてO(N)いては、全体で、O(N^2)となり、TLEになる。 - 一旦、奇数番目に
"A"がくるパターンと"B"がくるパターンで分けて考えて、片方の解放がわかれば良さそう。 - 結局、互いの同じアルファベット同士を交差するのは無駄と気づく。
- よって、最終的な位置との差分を線形走査させれば、
O(N)でいけそう。
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- なんとか、最終形が `ABAB...ABAB` or `BABA...BABA` であることを見抜く。
- その形にするために、一つ一つの文字 `O(N)` を具体的に動かして `O(N)` いては、全体で、`O(N^2)` となり、`TLE` になる。
- 一旦、奇数番目に `"A"` がくるパターンと `"B"` がくるパターンで分けて考えて、片方の解放がわかれば良さそう。
- 結局、互いの同じアルファベット同士を交差するのは無駄と気づく。
- よって、最終的な位置との差分を線形走査させれば、`O(N)` でいけそう。
"""
# 入力
N = int(input())
S = input()
ans = float("inf")
# 奇数番目の文字列
for A in ["A", "B"]:
cnt = 0
ind = 0
# 線形走査
for i, a in enumerate(S):
# ターゲットの文字列であったとき、
if(A == a):
# 最終的な位置との差分を加える
cnt += abs(ind - i)
# 次の最終的な位置を取得する。
ind += 2
# 最適解を更新
ans = min(ans, cnt)
# 出力
print(ans)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- 全てが忙しいので、ABCだけにします🙇（今回のDなんかむずくね？）