PythonでABC098-Cを解く

はじめに

PyBegiの人が解いてたので、便乗して解きます。

ABC098-C Attention

考えたこと
問題の制約的に最大でも$O(N)$程度で収めないといけないので、それぞれのリーダーごとに計算していては間に合わない。そこで、累積和を使います。これで毎回$sum$しなくても各リーダーごとに計算できます。ちなみに、Pythonの$sum$の計算量は$O(N)$です。ここまで分かったらやるだけ。

n = int(input())
s = input()

count_e = [0] * n
count_w = [0] * n
for i in range(n):
    if i == 0:
        if s[i] == 'E':
            count_e[i] = 1
        else:
            count_w[i] = 1
        continue
    if s[i] == 'E':
        count_e[i] = count_e[i-1] + 1
        count_w[i] = count_w[i-1]
    else:
        count_e[i] = count_e[i-1]
        count_w[i] = count_w[i-1] + 1

ans = 10 ** 9 #e+wは高々3*10**5程度ですが、余裕を持たせています
for i in range(n):
    if s[i] == 'E':
        e = count_e[-1] - count_e[i] #累積和を使う
        w = count_w[i]
    else:
        e = count_e[-1] - count_e[i] #累積和を使う
        w = count_w[i] - 1 #自分の分を引く
    ans = min(ans,e+w)
print(ans)

まとめ

制約を見て使えるアルゴリズムを思いつけるようになってきているので嬉しい。ではまた、おやすみなさい。