問題一覧 > 通常問題

No.2276 I Want AC

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 138
作問者 : miscalcmiscalc / テスター : magstamagsta
6 ProblemId : 8706 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-04-22 00:13:20

問題文

A, C, ? からなる長さ $N$ の文字列 $S$ が与えられます。

あなたは、$S$ に対して次の操作を行います。

  • $S$ に含まれる ? を、それぞれ A または C のいずれかで書き換える。

操作後、$S$ から（連続するとは限らない）部分列として AC を取り出す方法の数が得点となります。ここで、部分列を取り出す方法が異なるとは、取り出す位置が異なることをいいます。

得点の最大値を求めてください。

入力

$N$
$S$

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

出力

得点の最大値を出力してください。最後に改行してください。

サンプル

サンプル1
入力
5
A?CA?
出力
5

たとえば $S = $ AACAC とした場合、$S$ から（連続するとは限らない）部分列 AC を取り出す方法は

  • $1$ 文字目と $3$ 文字目を取り出す
  • $1$ 文字目と $5$ 文字目を取り出す
  • $2$ 文字目と $3$ 文字目を取り出す
  • $2$ 文字目と $5$ 文字目を取り出す
  • $4$ 文字目と $5$ 文字目を取り出す
の $5$ 通りがあります。よって得点は $5$ になります。

他に操作後の $S$ としてありうる文字列とその得点は、以下のようになります。

  • $S = $ AACAA とした場合、得点は $2$
  • $S = $ ACCAA とした場合、得点は $2$
  • $S = $ ACCAC とした場合、得点は $4$
よって、$S = $ AACAC が最大値 $5$ を達成することがわかります。

サンプル2
入力
6
ACACAC
出力
6

$S$ が ? を含まないこともあります。

サンプル3
入力
10
??????????
出力
25

$S = $ AAAAACCCCC とするのが最適です。

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