ABC328 python Atcoderの記録

問題はこちら
4完

A
カッコつけた書き方をしているがfor文とif文で丁寧にやればOKのはず

N, X =  list(map(int, input().split()))
S =  list(map(int, input().split()))
print(sum(i for i in S if i <= X))

B
ある日付の数字が同じかどうか判定するためにsetを使った（setに入れた要素のうち重複するものは削除されるため）。

N = int(input())
D = [0] + list(map(int, input().split())) # Index1と月が対応するようにした
answer = 0
for month in range(1, N+1):
    for day in range(1, D[month] +1):
        if len(set(str(month) + str(day))) == 1:
            answer += 1
print(answer)

C
愚直にli~ri文字目までを取り出し隣り合う要素がいくつあるかをカウントすると、計算量が最大となるのは毎回1文字目からN文字目までを取り出すことをQ回繰り返すとき。
この時の最大計算量は、O（len(S)Q） = O（NQ） = 9×10¹⁰ > 10⁸なので間に合わないはず。

何回も同じ部分文字列で隣と比較するのは非効率なので最初に隣と同じかをチェックし、１文字目からi文字目までに同じ文字が隣り合う箇所がいくつあるかを求めておく。
i文字目からj文字目までに含まれる同じ文字が隣り合う箇所 = 1文字目からj文字目までに含まれる同じ文字が隣り合う箇所 - 1文字目からi文字目までに含まれる同じ文字が隣り合う箇所で求められる。

N, Q =  list(map(int, input().split()))
S = "0" + input() # IndexとN文字目を合わせる
same_list = [0] # Sのi文字目までに隣り合う文字が同じであることが何回起こったかを記録
for i in range(1,N+1):
    if S[i-1] == S[i]:
        same_list.append(same_list[i-1] + 1) # 条件を満たすなら＋1
    else:
        same_list.append(same_list[i-1]) # 条件を満たさないならそのまま
# print(same_list)
# 出力
for q in range(Q):
    l,r = list(map(int, input().split()))
    print(same_list[r] - same_list[l])

D
要復習
replaceを"ABC"がなくなるまで繰り返そうと思ったが、長い文字列だと間に合わない。
後から考えれば、”ABC”の検索はO（N）、ABCを最大で2×10⁵ ÷3 ≒ 6万回探すことになるので、計算量はO（10⁹）となってしまうため当たり前だが、、、
後ろから取り出すことに特化しているStackを使うことで効率的に取り出せる。

def remove_abc_substring(s):
    result = []
    stack = []

    for char in s:
        stack.append(char)

        # スタックの最後の3文字が "ABC" であれば、それを削除
        if len(stack) >= 3 and stack[-3:] == ['A', 'B', 'C']:
            stack.pop()
            stack.pop()
            stack.pop()

    result = ''.join(stack)
    return result

# 例
input_string =   input()

result_string = remove_abc_substring(input_string)
print(result_string)