AtCoder ABC 098 C --Attention Thinking about the answer

problem

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

Way of thinking leading up to the answer

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) $.

answer

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

AtCoder ABC 098 C --Attention Thinking about the answer
Atcoder ABC125 C --GCD on Blackboard
Solved AtCoder ABC 114 C-755 with Python3
[AtCoder commentary] Win the ABC165 C problem "Many Requirements" with Python!
[AtCoder explanation] Control the A, B, C problems of ABC182 with Python!
Atcoder ABC099 C --Strange Bank Separate Solution
[AtCoder explanation] Control the A, B, C problems of ABC186 with Python!
[AtCoder explanation] Control the A, B, C problems of ABC185 with Python!
ABC memorandum [ABC157 C --Guess The Number] (Python)
AtCoder ABC176
[AtCoder explanation] Control the A, B, C problems of ABC187 with Python!
AtCoder ABC177
[AtCoder explanation] Control the A, B, C problems of ABC184 with Python!
[AtCoder explanation] Control the A, B, (C), D problems of ABC165 with Python!
[AtCoder explanation] Control the A, B, C, D problems of ABC183 with Python!
[AtCoder explanation] Control the A, B, C, D problems of ABC181 with Python!
Solving with Ruby AtCoder ABC110 C String Manipulation
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
About the test
AtCoder ABC 174 Python
AtCoder ABC187 Python
AtCoder ABC188 Python
AtCoder ABC 175 Python
About the queue
Solve Atcoder ABC176 (A, B, C, E) in Python