概要

文字列 \(S\) に含まれる、# が連続する区間の個数を求めます。それぞれの区間の「最後の #」を数えれば答えが得られます。

考察

# の個数をそのまま数えると、同じかたまりに属する敷石を何度も数えてしまいます。例えば .##..#.# には # が \(4\) 個ありますが、かたまりは \(3\) 個です。

そこで、各かたまりの右端だけを数えることを考えます。あるマスがかたまりの右端である条件は、次の両方を満たすことです。

• そのマスが # である。
• そのマスが道の末尾、または次のマスが . である。

例えば .##..#.# では、左から \(3\) 番目、\(6\) 番目、\(8\) 番目のマスがこの条件を満たすため、答えは \(3\) です。

各かたまりには右端がちょうど \(1\) つあり、この条件を満たすマスは必ずかたまりの右端です。したがって、条件を満たすマスを数えれば、重複も数え漏れもありません。

この問題では、文字列を一度走査するだけで十分に高速に解けます。

アルゴリズム

コードに合わせて、文字列の添字を \(0\) から \(N-1\) とします。

1. 答えを表す変数 cnt を \(0\) にする。
2. 各添字 \(i\) について、次の条件を満たすなら cnt を \(1\) 増やす。
   • s[i] == '#'
   • i + 1 == n または s[i + 1] == '.'
3. cnt を出力する。

計算量

• 時間計算量: \(O(N)\)
  各マスを一度ずつ調べます。
• 空間計算量: \(O(N)\)
  入力文字列の保存に必要です。入力文字列以外の追加領域は \(O(1)\) です。

実装のポイント

• 末尾が # の場合も数える必要があります。 次のマスが . かどうかだけを判定すると、末尾まで続くかたまりを数え漏らします。

• コードの i + 1 == n || s[i + 1] == '.' では、先に末尾かどうかを判定しています。C++ の || は左側が真なら右側を評価しないため、末尾では次の文字を参照せずに判定できます。

• # が一つもない場合は cnt が \(0\) のまま、すべて # の場合は末尾だけが数えられて \(1\) となり、どちらも正しく処理できます。

  ソースコード

// 問題文から独立に実装: '#' の区間が終わる瞬間（# の次が . か末尾）を数える
#include <iostream>
#include <string>
int main() {
    int n; std::string s; std::cin >> n >> s;
    int cnt = 0;
    for (int i = 0; i < n; ++i) if (s[i] == '#' && (i + 1 == n || s[i + 1] == '.')) cnt++;
    std::cout << cnt << std::endl;
}

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