AtCoder ABC421 解いてみた(PythonでABC問題)

ABC421をやってみました

今回もリアルタイム参加は出来なかったので、コンテスト翌日に復習しました。

大体の時間を測って解いていたのですが、ABCまでは100分の時間内に解けたようです。C問題はちょっと難しめでしたかも。

D問題も考えれば解けそうな印象ではあるのですが、時間がたりず、ACになりそうな解法はできませんでした。

A - Misdelivery

最初に名簿をlistで作成します。その後、i番目の人がYさんかどうかを確認します。

N = int(input())

# 名簿を作成
S = []
for _ in range(N):
    S.append(input())

# 名簿を確認
X, Y = input().split()
X = int(X)
if S[X - 1] == Y:
    print("Yes")
else:
    print("No")

B - Fibonacci Reversed

ちょっとややこしい問題でした。A[10]まで求めればいいので、ループ回数はTLEにはならなさそうです。ですので、問題に書いてあるとおりに、足したり逆順にしたり整数にしたりする処理を実装すれば良いです。

X, Y = map(int, input().split())
A = []
A.append(0)
A.append(X) # a1 はX
A.append(Y) # a2 はY

# 3から10まで計算
for i in range(3,11):
    # 直前の2つの和を計算し、逆順にして追加
    x = A[i-1] + A[i-2]
    str_x = str(x)
    rev_x = str_x[::-1]
    value = int(rev_x)
    A.append(value)
print(A[10])

C - Alternated

単純化して考えると実装が楽でした。(私の場合、単純化するのがだいぶ時間かかってしまうのですが...)

• 文字はAとBの2種類だけなので、Aを適切な位置に配置すれば、Bはその隙間に入る
  • つまり、Aのことだけを考えれば良い
• 最終的な並びは、ABABAB... か BABABA のパターンのみ
  • この2パターンのうち、コストが小さいほうが答え
• Sの中で最初のAは、最終的な並びでも最初のA、2番目のAは2番目のA...N番目のAはN番目のAというふうに移動する
  • つまり、Aのインデックスをリストに保存しておき、そのインデックスと最終的なインデックスとの差分を計算すれば良い

N = int(input())
S = list(input())

# Aのインデックスを保存
a_indexes = []
for i in range(len(S)):
    if S[i] == 'A':
        a_indexes.append(i)

cost0 = 0   # ABABAB... のときのコスト
cost1 = 0   # BABABA... のときのコスト
# 各Aについて、コストを計算
for i in range(len(a_indexes)):
    cost0 += abs(a_indexes[i] - i * 2)
    cost1 += abs(a_indexes[i] - (i * 2 + 1))

# 最小コストを求める
answer = min(cost0, cost1)
print(answer)