Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 行 N 列のマス目があります.上から i 行目,左から j 列目のマスをマス (i,j) と表します.
各マスには整数がひとつずつ書き込まれており,はじめマス (i,j) に書き込まれている整数は A_{i,j} です.
あなたは次の操作を繰り返し行うことができます:
- 1\leq i, j\leq N を満たす整数 i,j および整数 x を選び,A_{i,j} に x を加える.この操作にはコストが |x| かかる.
正整数 d が与えられます.あなたの目標は次の条件が成り立つようにすることです:
- 上下左右の 4 方向に隣接する 2 マスに書き込まれている整数の差は d 以上である.より形式的には,次の 2 条件が成り立つ:
- 1\leq i\leq N-1, 1\leq j\leq N を満たす整数 i, j に対して |A_{i,j}-A_{i+1,j}|\geq d.
- 1\leq i\leq N, 1\leq j\leq N-1 を満たす整数 i, j に対して |A_{i,j}-A_{i,j+1}|\geq d.
この目標を,総コスト \frac12 dN^2 以下で達成してください.
制約
- 2\leq N\leq 500
- 1\leq d\leq 1000
- -1000\leq A_{i,j}\leq 1000
入力
入力は以下の形式で標準入力から与えられます.
N d A_{1,1} \cdots A_{1,N} \vdots A_{N,1} \cdots A_{N,N}
出力
一連の操作後のマス目の状態を次の形式で出力してください.
A_{1,1} \cdots A_{1,N} \vdots A_{N,1} \cdots A_{N,N}
条件を満たすマス目の状態が複数存在する場合には,そのどれを出力しても正解となります.総コストを最小化する必要はありません.
入力例 1
3 5 -2 1 3 3 -4 -4 0 1 3
出力例 1
-2 8 3 3 -9 -4 -2 8 3
次のように 4 回の操作を行うと,マス目の状態が出力例の通りになります.
- (i,j,x)=(1,2,7) として操作を行う.
- (i,j,x)=(2,2,-5) として操作を行う.
- (i,j,x)=(3,1,-2) として操作を行う.
- (i,j,x)=(3,2,7) として操作を行う.
コストの総和は 7+5+2+7=21 であり,これは \frac{1}{2}dN^2=\frac{45}{2} 以下です.
入力例 2
5 2 1 5 5 0 3 2 0 2 5 1 5 2 0 5 5 3 7 2 0 1 6 0 4 3 6
出力例 2
0 4 6 1 3 3 1 3 6 1 5 3 0 3 5 2 6 3 1 3 4 0 5 3 6
Score: 600 points
Problem Statement
There is a grid with N rows and N columns. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.
Each cell contains an integer. Initially, cell (i,j) contains the integer A_{i,j}.
You can repeatedly perform the following operation:
- Choose integers i and j such that 1\leq i, j\leq N and an integer x, and add x to A_{i,j}. The cost of this operation is |x|.
You are given a positive integer d. Your goal is to satisfy the following condition:
- The difference between the integers written in any two cells that are vertically or horizontally adjacent is at least d. More formally, the following two conditions are satisfied:
- |A_{i,j}-A_{i+1,j}|\geq d for all integers i and j such that 1\leq i\leq N-1 and 1\leq j\leq N.
- |A_{i,j}-A_{i,j+1}|\geq d for all integers i and j such that 1\leq i\leq N and 1\leq j\leq N-1.
Achieve this goal with a total cost of \frac12 dN^2 or less.
Constraints
- 2\leq N\leq 500
- 1\leq d\leq 1000
- -1000\leq A_{i,j}\leq 1000
Input
The input is given from Standard Input in the following format:
N d A_{1,1} \cdots A_{1,N} \vdots A_{N,1} \cdots A_{N,N}
Output
Print the state of the grid after the series of operations in the following format:
A_{1,1} \cdots A_{1,N} \vdots A_{N,1} \cdots A_{N,N}
If multiple grid states satisfy the condition, any of them will be accepted. There is no need to minimize the total cost.
Sample Input 1
3 5 -2 1 3 3 -4 -4 0 1 3
Sample Output 1
-2 8 3 3 -9 -4 -2 8 3
Perform the operation four times as follows to yield the grid shown in the sample output:
- Perform the operation with (i,j,x)=(1,2,7).
- Perform the operation with (i,j,x)=(2,2,-5).
- Perform the operation with (i,j,x)=(3,1,-2).
- Perform the operation with (i,j,x)=(3,2,7).
The total cost is 7+5+2+7=21, which is not greater than \frac{1}{2}dN^2=\frac{45}{2}.
Sample Input 2
5 2 1 5 5 0 3 2 0 2 5 1 5 2 0 5 5 3 7 2 0 1 6 0 4 3 6
Sample Output 2
0 4 6 1 3 3 1 3 6 1 5 3 0 3 5 2 6 3 1 3 4 0 5 3 6
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
正整数 x に対し,その各桁の和を f(x) と表すことにします.例えば f(331)=3+3+1=7, f(2024)=2+0+2+4=8, f(1)=1 です.
正整数 N が与えられます.次の条件をすべて満たす正整数 x をひとつ出力してください.
- 1\leq x< 10^{10000}
- 任意の整数 1\leq i\leq N に対して f(2^{i-1}x)>f(2^ix) が成り立つ.
制約
- 1\leq N\leq 50
入力
入力は以下の形式で標準入力から与えられます.
N
出力
条件を満たす正整数 x を出力してください.条件を満たす正整数 x が複数存在する場合には,そのどれを出力しても正解と見なされます.
入力例 1
3
出力例 1
89
x=89 に対して f(x)=17, f(2x)=16, f(4x)=14, f(8x)=10 より f(x)>f(2x)>f(4x)>f(8x) であり,条件を満たしていることが分かります.
他に x=539, x=890 なども条件を満たします.
Score: 600 points
Problem Statement
For a positive integer x, let f(x) denote the sum of its digits. For example, f(331)=3+3+1=7, f(2024)=2+0+2+4=8, and f(1)=1.
You are given a positive integer N. Print a positive integer x that satisfies all of the following conditions:
- 1\leq x< 10^{10000}
- f(2^{i-1}x)>f(2^ix) for all integers 1\leq i\leq N.
Constraints
- 1\leq N\leq 50
Input
The input is given from Standard Input in the following format:
N
Output
Print a positive integer x that satisfies the conditions. If multiple positive integers x satisfy the conditions, any of them will be accepted.
Sample Input 1
3
Sample Output 1
89
For x=89, it follows from f(x)=17, f(2x)=16, f(4x)=14, and f(8x)=10 that f(x)>f(2x)>f(4x)>f(8x), satisfying the conditions.
Some other integers that satisfy the conditions are x=539 and x=890.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
A
, B
からなる文字列 S が与えられます.
あなたはこの文字列に対して,次の操作を繰り返し行うことができます:
- S の中の連続する 3 文字であって
AAB
またはBAA
に等しいものをひとつ選び,その 3 文字を S から削除する(削除した後,残っている文字は連結される).
操作を行える回数の最大値を求めてください.
T 個のテストケースが与えられるので,それぞれについて答えを求めてください.
制約
- 1\leq T\leq 10^5
- S は
A
,B
からなる文字列である. - 1\leq |S|\leq 10^6
- 1 個の入力に含まれるテストケースについて,それらの |S| の総和は 10^6 以下である.
入力
入力は以下の形式で標準入力から与えられます.
T \text{case}_1 \vdots \text{case}_T
各テストケースは以下の形式で与えられます.
S
出力
T 行出力してください.i 行目には i 番目のテストケースについて,操作を行える回数の最大値を出力してください.
入力例 1
10 AABAAAB BAAAAABBA A B ABA BAA AAAAAA AAAABB AABABBAABBABAAAABBAA BBAAAAABAAAAABABAABA
出力例 1
2 3 0 0 0 1 0 2 5 6
1 番目,2 番目のテストケースについて,次が操作回数を最大化する方法の一例となります.
AABAAAB
→AAAB
→A
BAAAAABBA
→BAAABA
→BAA
→ (空文字列)
Score: 800 points
Problem Statement
You are given a string S consisting of characters A
and B
.
On this string, you can repeatedly perform the following operation:
- Choose three consecutive characters in S that are equal to
AAB
orBAA
, and delete those three characters from S (after deletion, the remaining characters are concatenated).
Find the maximum number of times you can perform this operation.
T test cases are given; solve each of them.
Constraints
- 1\leq T\leq 10^5
- S is a string consisting of
A
andB
. - 1\leq |S|\leq 10^6
- The sum of |S| over all test cases in a single input is at most 10^6.
Input
The input is given from Standard Input in the following format:
T \text{case}_1 \vdots \text{case}_T
Each test case is given in the following format:
S
Output
Print T lines. The i-th line should contain the maximum number of operations that can be performed for the i-th test case.
Sample Input 1
10 AABAAAB BAAAAABBA A B ABA BAA AAAAAA AAAABB AABABBAABBABAAAABBAA BBAAAAABAAAAABABAABA
Sample Output 1
2 3 0 0 0 1 0 2 5 6
For each of the first and second test cases, here is a possible way to perform the maximum number of operations:
AABAAAB
→AAAB
→A
BAAAAABBA
→BAAABA
→BAA
→ (empty string)
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1100 点
問題文
A
, B
からなる長さ N の文字列 S が与えられます.ただし,S に含まれる A
の個数は \frac{N+1}{2} 以下であることが保証されます.さらに,正整数列 (x_1, \ldots, x_{N-1}) が与えられます.
あなたはこの文字列に対して,次の操作を繰り返し行うことができます:
- 1\leq i\leq N-1 を満たす整数 i を選び,S の i 文字目と (i+1) 文字目をスワップする.この操作にはコストが x_i かかる.
あなたの目標は,S において A
同士が隣接しないようにすることです.この目標を達成するために必要なコストの総和としてありうる最小値を求めてください.
T 個のテストケースが与えられるので,それぞれについて答えを求めてください.
制約
- 1\leq T\leq 10^5
- 2\leq N\leq 10^6
- S は
A
,B
からなる長さ N の文字列である. - S に含まれる
A
の個数は \frac{N+1}{2} 以下である. - 1\leq x_i \leq 10^6
- 1 個の入力に含まれるテストケースについて,それらの N の総和は 10^6 以下である.
入力
入力は以下の形式で標準入力から与えられます.
T \text{case}_1 \vdots \text{case}_T
各テストケースは以下の形式で与えられます.
N S x_1 \ldots x_{N-1}
出力
T 行出力してください.i 行目には i 番目のテストケースについて,S において A
が隣接しないようにするために必要なコストの最小値を出力してください.
入力例 1
5 4 BAAB 3 4 5 5 BBBBB 1 2 3 4 7 BAAABBB 8 7 6 5 4 3 7 BAAABBB 100 7 6 5 4 3 20 BAABAABBBABAAABBBABB 12 85 37 44 25 14 36 29 71 53 15 47 13 80 14 74 53 76 19
出力例 1
3 0 13 15 133
- 1 番目のテストケースについて,i=1 として操作を行うことで S は
BAAB
→ABAB
と変化し,目標を達成できます.この場合コストの総和は x_1=3 です. - 2 番目のテストケースについて,操作を行わないことで目標を達成できます.この場合コストの総和は 0 です.
- 3 番目のテストケースについて,i=1, i=4 として操作を行うことで S は
BAAABBB
→ABAABBB
→ABABABB
と変化し,目標を達成できます.この場合コストの総和は x_1+x_4=13 です. - 4 番目のテストケースについて,i=4, i=3, i=5 として操作を行うことで S は
BAAABBB
→BAABABB
→BABAABB
→BABABAB
と変化し,目標を達成できます.この場合コストの総和は x_4+x_3+x_5=15 です.
Score: 1100 points
Problem Statement
You are given a string S of length N consisting of A
and B
. It is guaranteed that the number of A
s in S is at most \frac{N+1}{2}. Additionally, you are given a sequence of positive integers (x_1, \ldots, x_{N-1}).
On this string, you can repeatedly perform the following operation:
- Choose an integer i such that 1\leq i\leq N-1, and swap the i-th and (i+1)-th characters of S. The cost of this operation is x_i.
Your goal is to rearrange S so that no two A
s are adjacent. Find the minimum total cost required to achieve this goal.
T test cases are given; solve each of them.
Constraints
- 1\leq T\leq 10^5
- 2\leq N\leq 10^6
- S is a string of length N consisting of
A
andB
. - The number of
A
s in S is at most \frac{N+1}{2}. - 1\leq x_i \leq 10^6
- The sum of N over all test cases in a single input is at most 10^6.
Input
The input is given from Standard Input in the following format:
T \text{case}_1 \vdots \text{case}_T
Each test case is given in the following format:
N S x_1 \ldots x_{N-1}
Output
Print T lines. The i-th line should contain the minimum total cost required to rearrange S so that no two A
s are adjacent for the i-th test case.
Sample Input 1
5 4 BAAB 3 4 5 5 BBBBB 1 2 3 4 7 BAAABBB 8 7 6 5 4 3 7 BAAABBB 100 7 6 5 4 3 20 BAABAABBBABAAABBBABB 12 85 37 44 25 14 36 29 71 53 15 47 13 80 14 74 53 76 19
Sample Output 1
3 0 13 15 133
- For the first test case, performing the operation with i=1 changes S as
BAAB
→ABAB
, achieving the goal. The total cost in this case is x_1=3. - For the second test case, performing nothing achieves the goal. The total cost in this case is 0.
- For the third test case, performing the operation with i=1 and i=4 changes S as
BAAABBB
→ABAABBB
→ABABABB
, achieving the goal. The total cost in this case is x_1+x_4=13. - For the fourth test case, performing the operation with i=4, i=3, and i=5 changes S as
BAAABBB
→BAABABB
→BABAABB
→BABABAB
, achieving the goal. The total cost in this case is x_4+x_3+x_5=15.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1500 点
問題文
頂点に 1 から N の番号が付いた N 頂点の木が与えられます.木の i 番目の辺は頂点 u_i と頂点 v_i を結んでいます.
K=1, 2, \ldots, N に対して次の問題を解いてください:
1, 2, \ldots, K の番号のついた K 個の石があり,番号 i の石は頂点 i に置かれています. 次の操作を繰り返し行うことができます:
- 木の辺で接続された 2 頂点 u, v であって,u に石が置かれていて,v には石が置かれていないものを選ぶ.u に置かれている石を v に移動させる.
操作後の石の配置としてありうる個数を 998244353 で割った余りを求めてください.ただし,2 つの石の配置はある番号の石が置かれている頂点が異なる場合に区別します.
T 個のテストケースが与えられるので,それぞれについて答えを求めてください.
制約
- 1\leq T\leq 10^5
- 1\leq N\leq 2\times 10^5
- 1\leq u_i, v_i\leq N
- 与えられるグラフは木である.
- 1 個の入力に含まれるテストケースについて,それらの N の総和は 2\times 10^5 以下である.
入力
入力は以下の形式で標準入力から与えられます.
T \text{case}_1 \vdots \text{case}_T
各テストケースは以下の形式で与えられます.
N u_1 v_1 \vdots u_{N-1} v_{N-1}
出力
T 行出力してください.i 行目には i 番目のテストケースについて,K=1, 2, \ldots, N に対する答えを半角スペース区切りで出力してください.
入力例 1
1 4 1 2 1 3 1 4
出力例 1
4 12 4 1
石の配置を番号 1, 2, \ldots, K の石が置かれている頂点の番号の列により表すと,
- K=1 の場合,ありうる石の配置は (1), (2), (3), (4) の 4 個です.
- K=2 の場合,ありうる石の配置は (1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3) の 12 個です.
- K=3 の場合,ありうる石の配置は (1,2,3), (4,1,3), (4,2,1), (4,2,3) の 4 個です.
- K=4 の場合,ありうる石の配置は (1,2,3,4) の 1 個です.
K=3 の場合について,次の図も参考にしてください.
入力例 2
4 1 5 1 4 5 2 3 4 2 1 7 1 7 2 7 5 6 4 1 1 6 3 6 10 1 2 2 3 3 4 4 5 5 6 2 7 3 8 4 9 5 10
出力例 2
1 5 10 10 5 1 7 42 210 840 84 7 1 10 90 720 5040 30240 151200 604800 720 10 1
それぞれのテストケースで与えられている木は次の図の通りです:
Score: 1500 points
Problem Statement
You are given a tree with N vertices numbered 1 to N. The i-th edge of the tree connects vertices u_i and v_i.
For each K=1, 2, \ldots, N, solve the following problem:
There are K stones numbered 1, 2, \ldots, K, with the stone numbered i placed on vertex i. You can repeatedly perform the following operation:
- Choose two vertices u and v connected by an edge such that u has a stone on it and v does not. Move the stone from u to v.
Find the number, modulo 998244353, of possible configurations of the stones after performing the operations. Two configurations are distinguished if and only if there is a stone whose position differs between those configurations.
T test cases are given; solve each of them.
Constraints
- 1\leq T\leq 10^5
- 1\leq N\leq 2\times 10^5
- 1\leq u_i, v_i\leq N
- The given graph is a tree.
- The sum of N over all test cases in a single input is at most 2\times 10^5.
Input
The input is given from Standard Input in the following format:
T \text{case}_1 \vdots \text{case}_T
Each test case is given in the following format:
N u_1 v_1 \vdots u_{N-1} v_{N-1}
Output
Print T lines. The i-th line should contain the answers for K=1, 2, \ldots, N for the i-th test case, separated by spaces.
Sample Input 1
1 4 1 2 1 3 1 4
Sample Output 1
4 12 4 1
Let us represent the configuration of stones by the sequence of vertices where the stones numbered 1, 2, \ldots, K are placed.
- For K=1, there are 4 possible configurations: (1), (2), (3), (4).
- For K=2, there are 12 possible configurations: (1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3).
- For K=3, there are 4 possible configurations: (1,2,3), (4,1,3), (4,2,1), (4,2,3).
- For K=4, there is 1 possible configuration: (1,2,3,4).
For K=3, refer to the following figure.
Sample Input 2
4 1 5 1 4 5 2 3 4 2 1 7 1 7 2 7 5 6 4 1 1 6 3 6 10 1 2 2 3 3 4 4 5 5 6 2 7 3 8 4 9 5 10
Sample Output 2
1 5 10 10 5 1 7 42 210 840 84 7 1 10 90 720 5040 30240 151200 604800 720 10 1
The tree given in each test case is as follows:
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1600 点
問題文
次の条件を満たす文字列を,美しい文字列ということにします.
- どの文字も
A
,B
,C
のいずれかである. - どの隣接する 2 文字も相異なる.
例えば AB
, BCAC
は美しい文字列です.BB
, CBAAC
は美しい文字列ではありません.
美しい文字列 S が与えられます.あなたはこの文字列に対して,次の操作を繰り返し行うことができます:
- 操作:S の隣接する 2 文字をスワップする.ただしスワップ後の S も美しい文字列でなくてはならない.
最終的な文字列 S としてありうる辞書順最小の文字列を求めてください.
T 個のテストケースが与えられるので,それぞれについて答えを求めてください.
制約
- 1\leq T\leq 10^5
- S は美しい文字列である.
- 1\leq |S|\leq 10^6
- 1 個の入力に含まれるテストケースについて,それらの |S| の総和は 10^6 以下である.
入力
入力は以下の形式で標準入力から与えられます.
T \text{case}_1 \vdots \text{case}_T
各テストケースは以下の形式で与えられます.
S
出力
T 行出力してください.i 行目には i 番目のテストケースについて,最終的な文字列 S としてありうる辞書順最小の文字列を出力してください.
入力例 1
8 CAB ACBCB B AC BACBA BABABA ABCBCAC CBABACABCBABABC
出力例 1
ABC ABCBC B AC ABABC BABABA ABCACBC ABABACBCACBCBAB
1 番目,2 番目のテストケースについて,次が S を辞書順最小化する方法の一例となります.
CAB
→ACB
→ABC
ACBCB
→CABCB
→CBACB
→BCACB
→BCABC
→BACBC
→ABCBC
Score: 1600 points
Problem Statement
A string is called a beautiful string if and only if it satisfies the following conditions:
- Every character is
A
,B
, orC
. - No two adjacent characters are the same.
For example, AB
and BCAC
are beautiful strings, while BB
and CBAAC
are not.
You are given a beautiful string S. On this string, you can repeatedly perform the following operation.
- Operation: Swap two adjacent characters in S. Here, S must still be a beautiful string after the swap.
Find the lexicographically smallest string that S can become.
T test cases are given; solve each of them.
Constraints
- 1\leq T\leq 10^5
- S is a beautiful string.
- 1\leq |S|\leq 10^6
- The sum of |S| over all test cases in a single input is at most 10^6.
Input
The input is given from Standard Input in the following format:
T \text{case}_1 \vdots \text{case}_T
Each test case is given in the following format:
S
Output
Print T lines. The i-th line should contain the lexicographically smallest string that S can become for the i-th test case.
Sample Input 1
8 CAB ACBCB B AC BACBA BABABA ABCBCAC CBABACABCBABABC
Sample Output 1
ABC ABCBC B AC ABABC BABABA ABCACBC ABABACBCACBCBAB
For each of the first and second test cases, here is a possible way to lexicographically minimize S:
CAB
→ACB
→ABC
ACBCB
→CABCB
→CBACB
→BCACB
→BCABC
→BACBC
→ABCBC