Attention [AtCoder Beginner Contest 098 C]

atcoder.jp

累積和の問題です。

ある人 i をリーダーに選んだとき、向く方向を変える必要があるのは、

・i より左側にいる W
・i より右側にいる E

です。この2つの合計が最小になるようにリーダーを選びます。

長さ N+2 の配列 W と、同じく長さN+2 の配列 E を確保します。これらの配列の [1] ～ [N] の部分に、それぞれ累積和をとっていきます。ただし、W は左から、E は右からとります。

入力例1で、累積和をとり終わった2つの配列の中身を見てみます。

W	0	1	1	1	2	3	0
E	0	2	2	1	0	0	0

ある人をリーダーに選んだとき、例えば3番目の人をリーダーに選んだときに向きを変えなければならない人数は、以下の2か所の和に相当します。

番目		1	2	3	4	5
W	0	1	1	1	2	3	0
E	0	2	2	1	0	0	0

このような部分は配列内に N 個あり、それぞれ「1 ～ N 番目の人をリーダーに選んだときの、向きを変えなければいけない人の人数」に対応しています。

よって、これらの中の最小値が答えになります。

void solve () {　

	int n = nextInt();
	int[] W = new int[n+2];
	int[] E = new int[n+2];
	String s = next();

	if (s.charAt(0) == 'W') W[1]++;
	for (int i=1; i<n; i++) {
		char c = s.charAt(i);
		W[i+1] = W[i] + (c=='W'? 1 : 0);

	}

	if (s.charAt(n-1) == 'E') E[n]++;
	for (int i=n-2; i>=0; i--) {
		char c = s.charAt(i);
		E[i+1] = E[i+2] + (c=='E'? 1 : 0);
	}

	int min = maxInt;
	for (int i=0; i<n; i++) {
		min = Math.min(min, W[i]+E[i+2]);
	}

	out.println(min);

}