概要

各衛兵が守るマスに印を付け、最後に印が付いていないマスの数を数えます。

考察

衛兵が位置 \(i\) にいるとき、その衛兵が守るのは位置 \(i-1, i, i+1\) のうち、廊下の範囲内にあるマスです。

ここで、衛兵の人数を数えて「守られているマス数は人数の \(3\) 倍」とすると、次の理由で正しく計算できません。

• 端にいる衛兵は、廊下の外側のマスを守れません。
• 複数の衛兵が同じマスを守ることがあります。

そこで、各マスが守られているかを記録する配列 guarded を用意します。最初はすべて False とし、衛兵が守るマスを True にします。同じマスを何度 True にしても結果は変わらないため、重複を気にする必要はありません。

例えば、\(N=5\)、S = "G.G.." の場合、左から \(1\) 番目の衛兵は \(1,2\) 番目を、\(3\) 番目の衛兵は \(2,3,4\) 番目を守ります。守られていないのは \(5\) 番目だけなので、答えは \(1\) です。

この問題では \(N \leq 100\) と小さく、各衛兵について守るマスをそのまま調べる方法で十分高速に解けます。

アルゴリズム

コードでは、マスの添字を \(0\) から \(N-1\) として扱います。

1. 長さ \(N\) の配列 guarded を、すべて False で初期化します。
2. 文字列 S を左から順に調べます。
   • S[i] が G なら、\(i-1, i, i+1\) を調べます。
   • その添字 \(j\) が \(0 \leq j < N\) を満たす場合、guarded[j] を True にします。
3. guarded に残っている False の個数を出力します。

すべての衛兵について、守るマスだけを True にするため、最後まで False のマスは、どの衛兵にも守られていないマスと一致します。

計算量

• 時間計算量: \(O(N)\)
  各マスを一度調べ、衛兵がいる場合も確認する位置は最大 \(3\) 個です。最後の個数の集計も \(O(N)\) です。
• 空間計算量: \(O(N)\)
  各マスが守られているかを記録する配列を使用します。

実装のポイント

• 添字が範囲内かを必ず確認します。 Python では guarded[-1] が末尾の要素を指すため、範囲確認を省くと、左端の衛兵が右端を守っているように記録してしまいます。

• 衛兵は自分のいるマスも守るため、左右だけでなく位置 \(i\) にも印を付けます。

• guarded.count(False) で、守られていないマスの数を求められます。

  ソースコード

# 問題文から独立に実装: 守られているマスに印を付けてから数える
n = int(input())
s = input().strip()
guarded = [False] * n
for i, c in enumerate(s):
    if c == 'G':
        for j in (i - 1, i, i + 1):
            if 0 <= j < n:
                guarded[j] = True
print(guarded.count(False))

---

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