[PYTHON] AtCoder ABC 098 C - Aufmerksamkeitsideen, die zur Antwort führen

Problem

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

Denkweise, die zur Antwort führt

Der zu beachtende Punkt ist, dass die Anzahl der ** Personen **, die sich umdrehen, wenn der Anführer $ i $ ist, abgefragt wird. Mit anderen Worten, es spielt keine Rolle, um welche Zahl sich die Person dreht. Daher ist es ausreichend, die Anzahl der nach Westen ausgerichteten Personen von $ 0 $ auf $ i -1 $ und die Anzahl der nach Osten ausgerichteten Personen von $ i + 1 $ auf $ N -1 $ zu addieren. Tun Sie dies für $ 0 \ leq i \ leq N - 1 $ und der Mindestwert ist die Antwort.

Um die Berechnungseffizienz zu verbessern, berechnen Sie die kumulative Summe der Anzahl der nach Westen ausgerichteten Personen und der Anzahl der nach Osten ausgerichteten Personen im Voraus, wenn $ 0 \ leq i \ leq N -1 $ und der Anführer der $ i $ th ist Die Anzahl der Personen, an die sie sich wenden, wird mit $ O (1) $ berechnet.

Antworten

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