atcoder練習(2024.11.24)

キーワード

問題

文字列 T が以下の条件を全て満たすとき、T を 11/22 文字列と呼びます。

|T| は奇数である。ここで、|T| は T の長さを表す。

1 文字目から (|T|+1)/2 - 1 文字目までが "1" である。

(|T|+1)/2 文字目が "/" である。

(|T|+1)/2 + 1 文字目から |T| 文字目までが "2" である。

例えば "11/22", "111/222", "/" は 11/22 文字列ですが、"1122", "1/22", "11/2222", "22/11", "//2/2/211" はそうではありません。

1, 2, / からなる長さ N の文字列 S が与えられます。S は / を 1 個以上含みます。11/22 文字列であるような S の(連続な)部分文字列の長さの最大値を求めてください。

制約

1 ≤ N ≤ 2 × 10^5

S は "1", "2", "/" からなる長さ N の文字列

S は / を 1 個以上含む

入力

入力は以下の形式で標準入力から与えられます。

N
S

出力

11/22 文字列であるような S の(連続な)部分文字列の長さの最大値を出力せよ。

入力例 1

8
211/2212

出力例 1

5

S の 2 文字目から 6 文字目からなる部分文字列は 11/22 で、これは 11/22 文字列です。S の部分文字列のうち 11/22 文字列であるものはこれが最長です。よって 5 が答えです。

入力例 2

5
22/11

出力例 2

1

入力例 3

22
/1211/2///2111/2222/11

出力例 3

回答

n = int(input())
s = input()
ans=0

for i in range(n):
  if s[i] == "/":
    key = 1
    for j in range(1, n//2+1):
      if i-j>=0 and i+j<=n-1 and s[i-j]=="1" and s[i+j]=="2":
        key += 2
      else:
        break
    ans = max(key,ans)
    
print(ans)

参考

備考

• すみません、答えみました。マジで分かりませんでした。elel6021様ありがとうございます。
• 全体的な挙動は理解しているもののの、正確な挙動は理解できていません。
• 自分の発想としては"1"を探す方法だったけど、この方法の方が綺麗そう。
• 全てのS[i]をfor文で探すこともできそうだけど、それだと実行時間が超過しそうな気がする。