概要

各マスについて、自分自身と左右の隣のマスに衛兵がいるかを調べます。どこにも衛兵がいなければ、そのマスは守られていないので答えに数えます。

考察

衛兵が守る範囲は、自分の立っているマスと、その左右の隣のマスだけです。

逆に、マス \(i\) が守られているかを知りたい場合は、次の最大 \(3\) マスだけを確認すれば十分です。

• 左隣のマス \(i-1\)
• マス \(i\) 自身
• 右隣のマス \(i+1\)

この中に G があればマス \(i\) は守られており、なければ守られていません。ただし、廊下の外に当たるマスは確認しません。

例えば、S = "G...G" の場合、左端の衛兵は左から \(1,2\) 番目のマスを、右端の衛兵は \(4,5\) 番目のマスを守ります。したがって、守られていないのは中央の \(1\) マスです。

各マスについてすべての衛兵を調べる素朴な方法でも、時間計算量は \(O(N^2)\) なので今回の制約では十分間に合います。ただし、確認する場所を上記の最大 \(3\) マスに絞れば、より効率よく処理できます。

なお、. の個数を数えるだけでは、衛兵の隣にある守られたマスまで数えてしまうため、正しい答えになりません。

アルゴリズム

文字列の添字を \(0\) から \(N-1\) として扱います。

1. 答えを格納する変数 ans を \(0\) にする。
2. 各マス \(i\) について、以下を行う。
   1. 守られているかを表す変数 guarded を False にする。
   2. \(j=i-1,i,i+1\) のそれぞれについて、\(0 \leq j < N\) かつ S[j] == 'G' なら、guarded を True にする。
   3. guarded が False のままなら、ans に \(1\) を加える。
3. ans を出力する。

マス \(i\) を守れる衛兵がいる場所は \(i-1,i,i+1\) に限られるため、この判定で守られていないマスを漏れなく数えられます。

計算量

• 時間計算量: \(O(N)\)
  各マスについて最大 \(3\) か所を確認します。
• 空間計算量: \(O(N)\)
  入力文字列の保存に必要です。入力を除く追加の作業領域は \(O(1)\) です。

実装のポイント

• 文字列にアクセスする前に、0 <= j < N で添字が範囲内かを確認します。特に Python では S[-1] が末尾の文字を指すため、この確認を省くと左端の判定を誤る可能性があります。

• 衛兵は自分自身のマスも守るので、左右だけでなく S[i] も確認します。

• guarded は、マスを調べるたびに False に初期化します。

  ソースコード

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    S = input().strip()
    ans = 0
    for i in range(N):
        guarded = False
        for j in (i - 1, i, i + 1):
            if 0 <= j < N and S[j] == 'G':
                guarded = True
        if not guarded:
            ans += 1
    print(ans)

main()

---

この解説は gpt-6-astra-medium によって生成されました。