ABC421 備忘録

今回はPythonでABC421をABCまで解くことができたので、その備忘録を纏めます。

コンテスト概要

AtCoder Beginner Contest 421

開催日:2025年8月30日 21:00-22:40

---

A - Misdelivery

N = int(input())
S = [input() for _ in range(N)]
X, Y = input().split()
X = int(X) - 1

if S[X] == Y:
    print("Yes")
else:
    print("No")

---

B - Fibonacci Reversed

方針📝

1. 数値を文字列にし、反転する関数の作成
2. 1で作成した関数を使って解くだけ

X, Y = map(int, input().split())

def f(x):
    return int(str(x)[::-1])

a_prev2 = X
a_prev1 = Y

for i in range(3, 11):
    a = f(a_prev1 + a_prev2)
    a_prev2, a_prev1 = a_prev1, a

print(a_prev1)

---

C - Alternated

最終的に作り形は

• ABABAB...（Aが偶数番目）
• BABABA...（Aが奇数番目）

のどちらかの交互ならびを作る事。どちらの形に揃えるかによって必要な入れ替え回数が変わるため、両方試して少ない方を選ぶ。

方針📝

1. Aの位置に注目する

• 入力文字列Sの中でAが現れる位置をposに格納
• 例えばS=ABBAABBの場合、pos=[0, 3, 4]

2. 目標の配置(target)を作る

• Aが来るべき位置を計算２通り
  • target1 = [0, 2, 4, ...] (Aが偶数番目)
  • target2 = [1, 3, 5, ...] (Aが奇数番目)

3. 移動コストの計算

• 実際の A の位置 pos と、理想の位置 target を 1対1で対応
• 必要な swap の回数は 「位置の差の総和」

abs(p-t)の総和がswqpの最小回数になる

# 例
N = 3
S = ABBAAB

• Aの位置：pos = [0, 3, 4]
• 交互並び（偶数開始）；target1 = [0, 2, 4]

対応させると：

pos = 0　⇨ target1 = 0 ⇨ 移動距離 0
pos = 3　⇨ target1 = 2 ⇨ 移動距離 1
pos = 4　⇨ target1 = 4 ⇨ 移動距離 0

合計 = 1となり、swap回数を求めることができる。

N = int(input())
S = input().strip()

pos = [i for i, ch in enumerate(S) if ch == "A"]

# Aが偶数番目
target1 = [2*i for i in range(N)]
ans1 = sum(abs(p - t) for p, t in zip(pos, target1))

# Aが奇数番目
target2 = [2*i+1 for i in range(N)]
ans2 = sum(abs(p - t) for p, t in zip(pos, target2))

print(min(ans1, ans2))

結果

ABC 3完
順位 3079th / 12891
パフォーマンス 1009
レーティング 1061 → 1052 (-9)