ARC098 C : Attention(300)

作成日:2018.09.29
最終更新日:2018.09.29

問題概要

問題本文

 $N$人の人が東西(EW)方向に一列に並んでおり、西から$i$番目に並んでいる人は方向$S_i$を向いている。 $N$人の中から$1$人を選び、その人以外の人をその人の方向に向かせる。 向く方向が変わる人の最小数を求めよ。
制約
$2 \leq N \leq 3 \times 10^5$
$|S| = N, \; S_i = {'E'},{'W'}$

考え方

 $i$番目の人を選んだとすると、向く方向が変わるのは$(i-1)$番目までの人で西を向いている人と$(i+1)$番目以降の人で東を向いている人である。 よってこのような人数が$O(1)$で求まれば、すべての人を選ぶのを試せば答えを求められる。 そしてこれは累積和を求める時と同様にすれば達成できる。 例えば先頭から$i$番目までの人で東を向いている人の数を事前に求めておけば良い。 以上により計算量$O(N)$で答えを求められる。

ソースコード

マクロ等はこちら

int N;
string S;
int e[300010];

int main(){
	cin >> N;
	cin >> S;
	repp(i,0,N) e[i+1] = e[i] + (S[i]=='E');
	int ans = N;
	repp(i,1,N+1) ans = min(ans,e[N]-e[i]+i-1-e[i-1]);
	cout << ans << endl;
	return 0;
}

解法まとめ

 先頭から$i$番目までの人で東を向いている人の数$e_i$を求める。(8行)
 $i$番目の人が選ばれた時は$(e_N$$-e_i$$+i-1$$-e_{i-1})$人が向きを変える必要がある。これらの最小値が答えである。(9-11行)

ARC098の他の問題 D E F

広告

自己紹介

赤になりたい競技プログラマー/バランス重視
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

広告