Universal Cup Judging System

Universal Cup

시간 제한: 2.0 s 메모리 제한: 1024 MB 총점: 100 해킹 가능 ✓
통계

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

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1417EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.