AtCoder ABC397 振り返り(緑コーダーがPythonでABC問題)

AtCoder ABC397 振り返り

オムロンプログラミングコンテスト2025（AtCoder Beginner Contest 397） - AtCoder

今回はABCの3問がACでした。今回はD問題以降の難易度が高かったらしく、3問正解だけでもレーティングは微減で済みました。

D問題は解説を見ると、数式を色々とあれこれしてたので、たしかに難しかったです...。もしかしたらE問題に着手するほうが良かったのでしょうか。

A - Thermometer

場合分けして解きました。小数点が入ると誤差が気になるところですが、今回は特に問題なかったようです。

X = float(input())
if X >= 38:
    print(1)
elif 38 > X >= 37.5:
    print(2)
else:
    print(3)

B - Ticket Gate Log

問題文の通り、文字列Sを先頭から一文字ずつ調べていきます。私は文字列Sの管理にdequeを使っていますが、そのまま文字列でも良いかもしれません(→公式解説)。
B問題としては、結構難しいような気もしました。

S = input()
queue = deque()
for s in S:
    queue.append(s)

pos = 1
count = 0 # 追加する文字数
last = ""
while queue:
    # 偶数番目で "o"なら　ok
    if pos % 2 == 0 and queue[0] == "o":        
        queue.popleft()
        last = "o"

    # 偶数番目で "i" なら、代わりに"o" を追加する
    elif pos % 2 == 0 and queue[0] == "i":        
        count += 1

    # 奇数番目で "i"なら　ok
    elif pos % 2 == 1 and queue[0] == "i":
        queue.popleft()
        last = "i"

    # 偶数番目で "o" なら、代わりに"i" を追加する
    elif pos % 2 == 1 and queue[0] == "o":
        count += 1

    pos += 1

# 最後が i のときは、o を追加する
if last == "i":
    count += 1

print(count)

C - Variety Split Easy

区切り位置を全探索し、そのたびに種類をカウントするのではTLEになってしまいます。そこで、あらかじめ種類を数えておきます。

数列Aを左から数えたときに、何種類が出現したか(fromleft)
数列Aを右から数えたときに、何種類が出現したか(fromright)

A = 3 1 4 1 5 なら
fromleft = 1 2 3 3 4 (種類)
fromright = 4 3 3 2 1 (種類)

これを最初に求めれば、区切り位置に対する種類数をすぐに求めることができます。

区切り位置が i のときの種類数は
count = fromleft[i] + fromright[i + 1]

N = int(input())
A = list(map(int, input().split()))

fromleft = [0] * N
fromright = [0] * N

# 左から調べたときの種類数(fromleft)を求める
tempset = set()
for i in range(N):
    tempset.add(A[i])
    fromleft[i] = len(tempset)

# 右から調べたときの種類数(fromright)を求める
tempset = set()
for i in range(N-1, -1, -1):
    tempset.add(A[i])
    fromright[i] = len(tempset)

# 区切り位置を変えて、最大値を求める
answer = 0
for i in range(N - 1):
    count = fromleft[i] + fromright[i + 1]
    answer = max(answer, count)

print(answer)