Conference* を解いたことがある人なら、自然とこの問題を思いつくかもしれません。
長さ $N$ の文字列 $S$ が与えられます。$S$ の各文字は A、B、C、? のいずれかです。特に、$S$ の先頭と末尾の文字は A です。
A、B、C のみからなる長さ $N$ の文字列に対し、そのスコアを、$i$ 文字目と $(i + 1)$ 文字目が異なるような整数 $i$($1 \le i \le N - 1$)の個数として定義します。
$Q$ 個のクエリが与えられます。$i$ 番目のクエリは以下の通りです:
非負整数 $X_i, Y_i, Z_i$ が与えられます。ここで、$X_i + Y_i + Z_i$ は $S$ に含まれる ? の個数に等しいです。$S$ に含まれる ? のうち $X_i$ 個を A に、$Y_i$ 個を B に、$Z_i$ 個を C に置き換えて得られるすべての文字列の中で、あり得る最大のスコアを出力してください。
入力
入力は以下の形式で与えられます:
N S Q X_1 Y_1 Z_1 X_2 Y_2 Z_2 : X_Q Y_Q Z_Q
出力
$Q$ 行出力してください。$i$ 行目には、$i$ 番目のクエリに対する答えを出力してください。
制約
- $N, Q, X_i, Y_i, Z_i$ は整数である。
- $2 \le N \le 3 \times 10^5$
- $S$ は
A、B、C、?からなる長さ $N$ の文字列である。 - $S$ の先頭と末尾の文字は
Aである。 - $1 \le Q \le 2 \times 10^5$
- $0 \le X_i$
- $0 \le Y_i$
- $0 \le Z_i$
- $X_i + Y_i + Z_i$ は $S$ に含まれる
?の個数に等しい。
入出力例
入力例 1
9 A??B??C?A 3 1 3 1 4 1 0 0 0 5
出力例 1
8 6 4
入力例 2
12 A???A?B????A 4 0 8 0 2 6 0 7 1 0 3 5 0
出力例 2
4 8 4 10
入力例 3
28 ACB??B???BCB??B????B?AAA?BBA 26 6 1 6 4 5 4 2 3 8 9 2 2 11 0 2 8 4 1 11 0 2 2 0 11 0 1 12 12 1 0 10 3 0 1 4 8 3 7 3 2 8 3 1 3 9 11 1 1 7 0 6 6 4 3 8 4 1 0 10 3 13 0 0 11 1 1 0 6 7 2 8 3 9 0 4 0 0 13
出力例 3
24 21 23 21 19 20 19 21 19 17 19 22 19 17 22 19 23 22 20 13 15 19 20 17 21 17
注記
最初の例において:
- 最初のクエリでは、文字を
ABCBABCBAのように置き換えるとスコアが $8$ となり、これがあり得る最大値です。 - 2 番目のクエリでは、文字を
ABABAACAAのように置き換えるとスコアが $6$ となります。 - 3 番目のクエリでは、文字を
ACCBCCCCAのように置き換えるとスコアが $4$ となります。
* https://www2.ioi-jp.org/camp/2025/2025-sp-tasks/contest3/conference-en.pdf