解説

各マス \(i\) について「守られているか」を判定します。マス \(i\) が守られるのは、\(S_i\) 自身が G、または左隣 \(S_{i-1}\) が G、または右隣 \(S_{i+1}\) が G のときです。左右の端では存在しない隣を参照しないよう、\(i > 0\) や \(i + 1 < n\) の条件で範囲チェックをします。

守られていないマスだけを数えて出力すればよいので、全マスを左から順に調べるだけで解けます。

正しさ

衛兵がいるマス \(j\) が守るのは \(j-1, j, j+1\) のみなので、マス \(i\) が守られる条件は「\(i-1, i, i+1\) のいずれかに衛兵がいる」ことと同値です。ループはこの条件を各マスについて正確に判定するため、数え上げられる個数は問題の定義と一致します。

計算量

各マスで定数個の参照を行うので時間計算量は \(O(N)\)、空間計算量は入力文字列を保持する \(O(N)\) です。