概要

文字列 \(S\) に含まれる、連続した # のかたまりの個数を求めます。. で文字列を分割し、空でない部分の数を数えれば解けます。

考察

同じかたまりに属する # の間には、. がありません。一方、異なるかたまりの間には必ず . があります。

したがって、. を区切りとして文字列を分割すると、空でない各部分が敷石のかたまりに対応します。

たとえば、.##..#.# を . で分割すると、次のようになります。

["", "##", "", "#", "#"]

空でない部分は "##"、"#"、"#" の \(3\) 個なので、答えは \(3\) です。

単に # の数を数えると、敷石の枚数を求めてしまい、かたまりの個数にはなりません。また、分割後の要素数をそのまま答えると、先頭や末尾の .、連続した . によって生じる空文字列まで数えてしまいます。そのため、空文字列を除いて数える必要があります。

なお、左から順番に調べる素朴な方法でも十分高速に解けます。今回は Python の文字列分割を使って簡潔に実装します。

アルゴリズム

1. \(N\) と \(S\) を読み込みます。
2. s.split('.') によって、文字列を . で分割します。
3. 分割して得られた部分のうち、空でないものを数えます。
4. その個数を出力します。

分割後の空でない部分は、すべて連続した # のみからなります。また、すべての敷石のかたまりがちょうど \(1\) つの部分として得られるため、この方法で正しい個数を求められます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

文字列の分割と、分割後の各部分の確認に合計 \(O(N)\) 時間かかります。また、分割結果を保持するために \(O(N)\) の空間を使います。

実装のポイント

答えを求めているのは、次の式です。

sum(1 for part in s.split('.') if part)

• s.split('.')：. を区切りにして文字列を分割します。
• if part：空文字列を除外します。Python では、空文字列は偽、空でない文字列は真として扱われます。
• sum(1 for ...)：条件を満たす部分ごとに \(1\) を足して、個数を求めます。

すべてが . なら空でない部分がないので \(0\)、すべてが # なら全体が \(1\) つの部分になるので \(1\) が出力されます。

ソースコード

# 問題文から独立に実装: '.' で分割して空でない部分の数
n = int(input())
s = input().strip()
print(sum(1 for part in s.split('.') if part))

---

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