AtCoder ABC 098 C - Idées d'attention menant à la réponse

problème

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

Pensée menant à la réponse

Le point à noter est que le nombre de personnes qui se retournent lorsque le leader est $ i $ est demandé. En d'autres termes, peu importe le nombre ** que la personne tourne. Il suffit donc d'ajouter le nombre de personnes faisant face à l'ouest de 0 $ à $ i -1 $ et le nombre de personnes faisant face à l'est de $ i + 1 $ à $ N -1 $. Faites ceci pour $ 0 \ leq i \ leq N --1 $ et la valeur minimale sera la réponse.

Pour améliorer l'efficacité du calcul, calculez à l'avance la somme cumulée du nombre de personnes faisant face à l'ouest et du nombre de personnes faisant face à l'est. Le nombre de personnes qui se tournent vers est calculé par $ O (1) $.

répondre

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 - Idées d'attention menant à la réponse
Atcoder ABC125 C --GCD sur tableau noir
Résolu AtCoder ABC 114 C-755 avec Python3
[Commentaire d'AtCoder] Gagnez le problème ABC165 C "Many Requirements" avec Python!
[Explication AtCoder] Contrôlez les problèmes A, B, C d'ABC182 avec Python!
Atcoder ABC099 C - Solution séparée de Strange Bank
Mémorandum ABC [ABC157 C --Guess The Number] (Python)
AtCoder ABC176
AtCoder ABC177
[Explication AtCoder] Contrôle ABC184 Problèmes A, B, C avec Python!
[Explication AtCoder] Contrôlez les problèmes A, B, (C), D de ABC165 avec Python!
[Explication AtCoder] Contrôlez les problèmes A, B, C, D d'ABC183 avec Python!
[Explication AtCoder] Contrôlez les problèmes A, B, C, D d'ABC181 avec Python!
Manipulation de chaîne C AtCoder ABC110 à résoudre dans Ruby
Défiez AtCoder (ABC) 164 avec Python! Un problème ~ C
À propos du test
AtCoder ABC 174 Python
AtCoder ABC 175 Python
À propos de la file d'attente
Résoudre Atcoder ABC176 (A, B, C, E) en Python