ABC098C - Attention

atcoder.jp

西側から「自分より西にいるのに西を向いている人の数」を数える。 同時に、東側から「自分より東にいるのに東を向いている人の数」も数える。 最後に、「自分より西にいるのに西を向いている人の数」と「自分より東にいるのに東を向いている人の数」の最小値を計算すれば OK。 計算量は O(2N) かな。

using System;

namespace ABC098C
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var S = Console.ReadLine();

            var W = new int[N];
            var E = new int[N];
            var wCount = 0;
            var eCount = 0;
            for (var i = 0; i < N; i++)
            {
                W[i] = wCount;
                if (S[i] == 'W')
                {
                    wCount++;
                }

                var j = N - i - 1;
                E[j] = eCount;
                if (S[j] == 'E')
                {
                    eCount++;
                }
            }

            var min = int.MaxValue;
            for (var i = 0; i < N; i++)
            {
                min = Math.Min(min, W[i] + E[i]);
            }
            Console.WriteLine(min);
        }
    }
}