問題一覧 > 通常問題

No.2276 I Want AC

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

問題文

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

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

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

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

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

入力

NN
SS

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

出力

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

サンプル

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

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

  • 11 文字目と 33 文字目を取り出す
  • 11 文字目と 55 文字目を取り出す
  • 22 文字目と 33 文字目を取り出す
  • 22 文字目と 55 文字目を取り出す
  • 44 文字目と 55 文字目を取り出す
の 55 通りがあります。よって得点は 55 になります。

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

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

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

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

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

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

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