どうもこんにちは！
今週のコンテストはCまで完答、振り返りもCまで。
Dは方針が全く思い浮かばずでした。
問題と公式の解説のリンク
問題は以下のリンクから。
A - Misdelivery -
問題
n個の文字列が1から順番に与えられ、次に与えられた番号xと文字列yが先に与えられたx番目の文字列と一致するかを判定する問題。
考え方とコード
素直にif文で判定しました。
n = int(input())
s = []
for _ in range(n):
s.append(input())
a,b = map(str,input().split())
print("Yes" if s[int(a)-1] == b else "No")
B - Fibonacci Reversed -
問題
$a_{1}$と$a_{2}$が与えられ、フィボナッチ数列のように$a_i = a_{i-1} + a_{i-2} (i >= 3)$で計算していき、計算結果が10以上の場合は数字を反転するとします。例えば1234なら4321にするイメージ。こうして数列を作るとしたときの$a_{10}$を出力する問題。
考え方とコード
$a_i$が10以上の場合だけいったん文字列にしてスライスで反転して数値に戻すという処理で対応しました。フィボナッチの計算方法も含めてスマートなやり方があったはずですが思い出せず、早く実装するのを優先しました。
x,y = map(int,input().split())
a = [x,y]
for i in range(2,10):
tmp = a[i-1] + a[i-2]
if tmp >= 10:
tmp = int(str(tmp)[::-1])
a.append(tmp)
print(tmp)
C - Alternated -
問題
AとBがそれぞれN個ずつ含まれた文字列が与えられます。この文字列に対して、隣り合う文字列を最低何回入れ替えたらAとBが交互に来る文字列になるかを出力する問題。例えばAABBならABABにする、またBBAAならBABAにするイメージです。
文字数の最大は$10^6$。
考え方とコード
最終的にAから始まるならAが奇数文字目、Bが偶数文字目に来ます。(Bから始まるなら偶奇が反対)
そこで、文字列を前から見て上記と異なる位置にいる文字の場所を文字ごとに保持しつつ、AとBの入れ替え回数を計算するとしました。例えばAAABBBの場合、2番目のAと5番目のBを入れ替えればよく、入れ替え回数は5-2で3回です。
一方、答えの文字列がABどちらから始まるかを判断する方法は思いつかず、割り切ってAが最初の場合とBが最初の場合をそれぞれ計算し、最小となった方を出力しました。
from collections import deque
n = int(input())
s = list(input())
# Aが最初の文字になる場合の計算
a,b = deque(), deque()
ans_a = 0
for i in range(n*2):
if i % 2 == 0 and s[i] == 'B':
if len(a) == 0:
b.append(i) # Bの位置を記録
else:
ans_a += i - a.pop() # 先に把握しているAとの入れ替え回数を加算
if i % 2 == 1 and s[i] == 'A':
if len(b) == 0:
a.append(i) # Aの位置を記録
else:
ans_a += i - b.pop() # 先に把握しているBとの入れ替え回数を加算
# Bが最初の文字になる場合の計算
a,b = deque(), deque()
ans_b = 0
for i in range(n*2):
if i % 2 == 0 and s[i] == 'A':
if len(b) == 0:
a.append(i)
else:
ans_b += i - b.pop()
if i % 2 == 1 and s[i] == 'B':
if len(a) == 0:
b.append(i)
else:
ans_b += i - a.pop()
print(min(ans_a,ans_b))
次回のABC422はお休みの予定です。
日曜日の昼はさすがに予定をあわせにくいということで・・・
ではでは。