C - Attention https://atcoder.jp/contests/abc098/tasks/arc098_a
The point to note is that the number of people who turn around when the leader is $ i $ is asked. In other words, it doesn't matter what number ** the person turns around. Therefore, it is sufficient to add the number of people facing west from $ 0 $ to $ i -1 $ and the number of people facing east from $ i + 1 $ to $ N -1 $. Do this for $ 0 \ leq i \ leq N --1 $ and the minimum value will be the answer.
To improve the calculation efficiency, calculate the cumulative sum of the number of people facing west and the number of people facing east in advance. The number of people who turn to is calculated by $ 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))
Recommended Posts