解法

各マス \(i\)（\(1 \leq i \leq N\)）について、「衛兵に守られているか」を独立に判定すればよい。

マス \(i\) は、位置 \(i-1\), \(i\), \(i+1\)（存在するもののみ）のいずれかに衛兵が立っているとき、かつそのときに限り守られている。つまり、マス \(i\) がどの衛兵にも守られていないことと、以下の3条件がすべて成り立つことは同値である。

• \(S_i\) が . である（自分のマスに衛兵がいない）
• \(i = 1\) または \(S_{i-1}\) が . である（左隣に衛兵がいない）
• \(i = N\) または \(S_{i+1}\) が . である（右隣に衛兵がいない）

したがって、全マスを左から順に調べ、上の条件を満たすマスの個数を数えればよい。

正しさの証明

衛兵が位置 \(j\) にいるとき、彼が守るマスは \(\{j-1, j, j+1\} \cap \{1, \dots, N\}\) である。よってマス \(i\) が守られるのは、\(i \in \{j-1, j, j+1\}\) すなわち \(j \in \{i-1, i, i+1\}\) を満たす衛兵 \(j\) が存在するとき、かつそのときに限る。これは \(S_{i-1}, S_i, S_{i+1}\)（存在するもののみ）の少なくとも一つが G であることと同値であり、その否定が上記の3条件である。アルゴリズムは各マスについてこの条件を正確に検査し、真となる個数を出力するので、求める答えと一致する。

計算量

• 時間計算量: \(O(N)\)（各マスについて高々3マスを調べる）
• 空間計算量: 入力文字列を除けば \(O(1)\)

\(N \leq 100\) なので十分に高速である。