問題一覧 > 通常問題

No.2276 I Want AC

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 155
作問者 : miscalc / テスター : magsta
お気に入りにしたユーザー ProblemId : 8706 / 自分の提出
問題文最終更新日: 2023-04-22 00:13:20
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 385 (順位表) の他の問題:

Problem Statement

You are given a string $S$ of length $N$ consisting of A, C, and ?.

You perform the following operation on $S$.

  • Replace each ? in $S$ with either A or C.

After the operation, the score is the number of ways to extract AC as a (not necessarily contiguous) subsequence from $S$. Here, two ways of extracting a subsequence are considered different if the extracted positions are different.

Find the maximum possible score.

Input

$N$
$S$

  • $N$ is an integer.
  • $2 \leq N \leq 2 \times 10^5$
  • $S$ is a string of length $N$ consisting of A, C, and ?.

Output

Output the maximum possible score, followed by a newline.

Sample

Sample 1
Input
5
A?CA?
Output
5

For example, if we make $S = $ AACAC, the ways to extract the (not necessarily contiguous) subsequence AC from $S$ are the following

  • Extract the $1$-st and $3$-rd characters
  • Extract the $1$-st and $5$-th characters
  • Extract the $2$-nd and $3$-rd characters
  • Extract the $2$-nd and $5$-th characters
  • Extract the $4$-th and $5$-th characters
for a total of $5$ ways. Thus, the score is $5$.

The other strings $S$ possible after the operation and their scores are as follows.

  • If $S = $ AACAA, the score is $2$.
  • If $S = $ ACCAA, the score is $2$.
  • If $S = $ ACCAC, the score is $4$.
Therefore, $S = $ AACAC achieves the maximum value $5$.

Sample 2
Input
6
ACACAC
Output
6

$S$ may contain no ?.

Sample 3
Input
10
??????????
Output
25

Making $S = $ AAAAACCCCC is optimal.

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