1 of 4

A:Hello ACPC

FA(全体): noya2 (1:19)

FA(オンサイト): touhokudai (1:28)

AC/Try: 29/42

原案：zawatin

問題準備・解説: kota1t

2 of 4

問題概要

・長さNの文字列が与えられる。（Nは最大 200000）

・文字は「A」「C」「P」のいずれか

・「ACPC」という部分文字列を含ませたい

・「ACPC」がすでにあれば変更は不要

・含まれていない場合、最小の変更回数で「ACPC」を作る必要がある

​

3 of 4

考え方

・「ACPC」の文字列を作るためには、連続した４文字を調べる必要がある。

・文字列を左から順に見ていき、４文字ずつチェックする

　・「ACPC」との違いが最も少ない部分を探す

　・最も少ない変更回数が答えになる

・一回のチェックは4文字だけなので、各部分文字列をO(1)で確認できる。

・これを文字列全体で行うので、全体の計算量はO(N)になる。

4 of 4

解答例（C++）