AtCoder ABC381 振り返り (Python A~D)

abc381のA,B,C,DをPythonで。
本番ではA~Cの3完でした(Cは2TEL,1WA)。Dはコンテスト中の考察をコンテスト後にACしたコードです。


# A問題
### 問題概要
条件を満たす文字列を**11/22文字列**を呼ぶ。与えられた文字列か**11/22文字列**か判定せよ。
### 解答
条件をすべてやる。添え字の扱いに注意
```python
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にする。
```python
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の最大値
```python
# /の位置を求める
# /の左右を見ていき、左右の数字の塊がなくなったら、(塊の小さい方) * 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)
```
### コンテスト後の解答
`/`が来たら左右の文字が条件を満たすか数えてもできる。
```python
# 全探索していき、/か来たら、左右の文字を調べる
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(スライスの長さ)と時間がかかる。
```python
# /の位置を求める
# /の左右を見ていき、左右の数字の塊がなくなったら、(塊の小さい方) * 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を越してしまうため、対策する。
```python
# 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問題は何となくわかりそうなところまで行くが、その後の詰めが甘いので、精進する必要がある。次回はレートがプラスになるよう頑張りたい。