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