AtCoder ABC 098 C - Attention 解答に至るまでの考え方

問題

C - Attention https://atcoder.jp/contests/abc098/tasks/arc098_a

解答に至るまでの考え方

注目すべきポイントは、リーダーを $i$ 番目としたときに向きを変える 人数 が問われていること。すなわち向きを変える人が 何番目 かは問われていない。よって、 $0$ から $i - 1 $ 番目までで西を向いている人数と $i + 1$ から $N - 1$番目までで東を向いている人数を足せば良いと分かる。この操作を $0 \leq i \leq N - 1$ で行い最小値が解答となる。

計算効率を上げるには、西を向いている人数と東を向いている人数の累積和を予め求めておけば、$0 \leq i \leq N - 1$ でリーダーを $i$ 番目としたときに向きを変える人数を $O(1)$ で求められる。

解答

Pythonです。

N = int(input())
S = input()
int_s = [0] * N
cum_sum_w = [0] * (N + 1)
cum_sum_e = [0] * (N + 1)
answers = [0] * N
for i in range(N):
    if (S[i] == 'W'):
        int_s[i] = 1
    else:
        int_s[i] = 0
    cum_sum_w[i + 1] = cum_sum_w[i] + int_s[i]
for i in range(N):
    if (S[i] == 'E'):
        int_s[i] = 1
    else:
        int_s[i] = 0
    cum_sum_e[i + 1] = cum_sum_e[i] + int_s[i]
for i in range(N):
    answers[i] = cum_sum_w[i] + (cum_sum_e[N] - cum_sum_e[i + 1])
print(min(answers))