ARC98 C問題をC++で解く

タイトルの通りARC98のC問題をC++で解いた話です。
問題のリンク

今回は累積和を用いて解きました。
累積和についてピンと来ない方は以下の記事が個人的におすすめです。
累積和を何も考えずに理解する: https://qiita.com/drken/items/56a6b68edef8fc605821

解法

今回求めたいものを少し言い換えると、

リーダーの左側にいるWを向いている人 + リーダーの右側にいるEを向いている人

が最小になるようにリーダーを決めると取ることが出来ます。
ということは、与えられたSの先頭からそれぞれリーダーにした場合を考えると解けます。
ただこの解法だとO(N^2)となってしまいTLEになってしまいます。

そこで累積和を用いました。
先頭からEを向いている人とWを向いている人をそれぞれ累積和をとってあげるとO(N*2)程度になるのでTLEを回避できます。

もう少し詳細に書きます。
先頭からEを向いている人をEast, 先頭からWを向いている人をWestという配列を用いて累積和を作っていきます。
(予めそれぞれの配列に初期値0を挿入しておく)

入力例に
5
WEEWW
が来た場合、それぞれの配列の中身は、
East = [0, 0, 1, 2, 2, 2]
West = [0, 1, 1, 1, 2, 3]
になります。

そしてリーダーの左側にいるWを向いている人 + リーダーの右側にいるEを向いている人は、

East[一番最後] - East[リーダーの位置] + West[リーダーの位置-1]

で表現することが出来ます。

自分の解答