問題一覧 > 通常問題

No.2021 Not A but B

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 174
作問者 : milkcoffeemilkcoffee / テスター : first_vilfirst_vil
2 ProblemId : 7969 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-07-27 14:39:01

問題文

A, B からなる長さ $N$ の文字列 $S$ が与えられます。あなたは以下の操作を $S$ に対してちょうど $1$ 回だけ行います。

  • $S$ の連続する $2$ 文字を選び、その $2$ 文字をどちらも B に置き換える。

    • 操作後の文字列 $S$ としてあり得るのは何通りですか。

    入力

    $N$
$S$

  • $2 \leq N \leq 2 \times 10^5$
  • $N$ は整数である
  • $S$ は A, B からなる長さ $N$ の文字列

    • 出力

    操作後の $S$ としてあり得る $S$ の通り数を整数で出力してください。

    サンプル

    サンプル1
    入力
    4
AABA
    出力
    3

    あり得るのは以下の $3$ 通りです。
    BBBA
    ABBA
    AABB

    サンプル2
    入力
    3
ABB
    出力
    2

    あり得るのは以下の $2$ 通りです。
    BBB
    ABB

    サンプル3
    入力
    7
ABABABA
    出力
    4

    あり得るのは以下の $4$ 通りです。
    BBABABA
    ABBBABA
    ABABBBA
    ABABABB

    サンプル4
    入力
    40
ABBAABABAAABABBAABABAAABAAABBABAAAABBABA
    出力
    31

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。