abc381のA,B,C,DをPythonで。
本番ではA~Cの3完でした(Cは2TEL,1WA)。Dはコンテスト中の考察をコンテスト後にACしたコードです。
A問題
問題概要
条件を満たす文字列を11/22文字列を呼ぶ。与えられた文字列か11/22文字列か判定せよ。
解答
条件をすべてやる。添え字の扱いに注意
n = int(input())
s = input()
ans = "Yes"
if n % 2 == 0:
ans = "No"
elif s[0 : (n + 1) // 2 - 1] != "1" * ((n + 1) // 2 - 1):
ans = "No"
elif s[(n + 1) // 2 - 1] != "/":
ans = "No"
elif s[(n + 1) // 2 :] != "2" * ((n) // 2):
ans = "No"
print(ans)
B問題
問題概要
条件を満たす文字列を112文字列と呼ぶ。与えられた文字列が1122文字列か判定せよ。
解答
答えをYesにしておく。奇数だったらNo。前から2文字ずつ見る。setで出現した文字を記録して、二つの文字が一致しないか、出現済みの文字が出たらNoにする。
s = input()
ans = "Yes"
if len(s) % 2 != 0:
ans = "No"
else:
# 2, 3の条件を満たすかチェック
# 隣り合う文字列が同じならok
exist_char = set()
for i in range(0, len(s), 2):
if s[i] != s[i + 1]:
ans = "No"
break
if s[i] in exist_char:
ans = "No"
break
exist_char.add(s[i])
print(ans)
C問題
問題概要
与えられた文字列の中で、11/22文字列となる連続な部分文字列の最大値を求める。
コンテスト中の解答
前から連続する1を数える。/が出現したら、フラッグを立てて、直後の連続する2を数える。
答えは(1の連続数と2の連続数の小さい方)*2+1の最大値
# /の位置を求める
# /の左右を見ていき、左右の数字の塊がなくなったら、(塊の小さい方) * 2 + 1を答えに
n = int(input())
s = input()
ans = 1
is_right = False
left = 0 # 連続する1のみ数える
right = 0 # 連続する2のみ数える
for i in range(n):
if not is_right:
if s[i] == "1":
left += 1
elif s[i] == "2":
left = 0
elif is_right:
if s[i] == "2":
right += 1
elif s[i] != "2":
right = 0
left = 0
if s[i] == "1":
left += 1
is_right = False
if s[i] == "/":
is_right = True
# print(f"{i=}, {left=}, {right=}, {ans=}")
ans = max(ans, (min(left, right) * 2) + 1)
print(ans)
コンテスト後の解答
/が来たら左右の文字が条件を満たすか数えてもできる。
# 全探索していき、/か来たら、左右の文字を調べる
n = int(input())
s = input()
ans = 0
for i in range(n):
if s[i] == "/":
d = 0
while True:
left = i - d - 1
right = i + d + 1
if left < 0 or right >= n:
break
if s[left] != "1" or s[right] != "2":
break
d += 1
ans = max(ans, d * 2 + 1)
print(ans)
(参考)TELした解答
11/22文字列の判定をスライスを使って求めようとした。
インデックス指定はO(1)に対して、スライスはO(スライスの長さ)と時間がかかる。
# /の位置を求める
# /の左右を見ていき、左右の数字の塊がなくなったら、(塊の小さい方) * 2 + 1を答えに
n = int(input())
s = input()
ans = 1
indices = [i for i in range(n) if s[i] == "/"]
count = 1
# 得られたindicesを使って、/の左右を見ていく
for i in indices:
while True:
# print(s[i - count : i], s[i + 1 : i + count + 1])
if i - count < 0 or i + count >= n:
break
if (
s[i - count : i] == "1" * count
and s[i + 1 : i + count + 1] == "2" * count
):
count += 1
else:
break
count -= 1
ans = max(ans, count * 2 + 1)
print(ans)
D問題
問題概要
条件を満たした数列を1122数列と呼ぶ。与えられた数列の連続する部分列で、1122数列となる最長のものの長さを求めよ。
コンテスト中の考察
- 2つ飛ばしの尺取り法で出来そう
- 偶数番目スタートの場合は判定できるが、奇数番目スタートの場合が判定できない
- 一般化できず終了
コンテスト後の解答
無理に一般化せず偶奇分けて尺取り法をする。
場合によっては、leftがrightを越してしまうため、対策する。
# 2個飛ばしの尺取り法
# 偶奇で分ける
# 現れる数はsetで管理
n = int(input())
a = list(map(int, input().split()))
ans = 0
for left in range(2):
right = left
exit_num = set()
for left in range(left, n, 2):
while right + 1 < n:
if a[right] != a[right + 1] or a[right] in exit_num:
break
exit_num.add(a[right])
right += 2
ans = max(ans, right - left)
if left == right:
right += 2
exit_num.discard(a[left])
print(ans)
追記
D問題の公式解説にある解法2がよくわからなかった。分かる人がいたら教えてください。
感想
最近負けてばっかなのが悔しい。今回のC問題はスライスの計算量を考えずの実装のせいでTLEをしてしまったことが反省点。D問題は何となくわかりそうなところまで行くが、その後の詰めが甘いので、精進する必要がある。次回はレートがプラスになるよう頑張りたい。