Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
A
, B
からなる長さ N の文字列 S が与えられます。
あなたは、以下の操作を 0 回以上好きな回数繰り返すことができます。
- S の中の隣接する 2 文字を一ヶ所選び、
AB
で置き換える。
S を回文にできるか判定してください。
回文とは
ある文字列 T について、 T の長さを |T| として、全ての整数 i (1 \le i \le |T|) について、 T の前から i 文字目と後ろから i 文字目が同じであるとき、またそのときに限って、 T は回文です。制約
- 2 \leq N \leq 2\times 10^5
- S は
A
,B
からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
S を回文にできる場合は Yes
を、そうでない場合は No
を出力せよ。
入力例 1
3 BBA
出力例 1
Yes
2,3 文字目の BA
を操作により AB
で置き換えることで、S を回文である BAB
にできます。
入力例 2
4 ABAB
出力例 2
No
操作を何回行っても、S を回文にはできません。
Score : 400 points
Problem Statement
You are given a string S of length N consisting of A
and B
.
You can repeat the following operation zero or more times:
- choose a pair of adjacent characters in S and replace them with
AB
.
Determine whether S can be turned into a palindrome.
What is a palindrome?
A string T is a palindrome if and only if, for every integer i (1 \le i \le |T|), the i-th character from the beginning and the i-th character from the end are the same, where |T| is the length of T.Constraints
- 2 \leq N \leq 2\times 10^5
- S is a string of length N consisting of
A
andB
.
Input
Input is given from Standard Input in the following format:
N S
Output
If S can be turned into a palindrome, print Yes
; otherwise, print No
.
Sample Input 1
3 BBA
Sample Output 1
Yes
Replacing the 2-nd and 3-rd characters, BA
, with AB
will turn S into BAB
, a palindrome.
Sample Input 2
4 ABAB
Sample Output 2
No
No sequence of operations can turn S into a palindrome.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
以下のゲームをゲーム n と呼びます。
Alice と Bob でゲームをします。はじめ n 個の石があります。
Alice から始めて、交互に次の操作を行い、操作を行えなくなった方が負けとなります。
- もし Alice が操作を行うなら、石を A の正の倍数の個数取り除く。
- もし Bob が操作を行うなら、石を B の正の倍数の個数取り除く。
ゲーム 1、ゲーム 2、…、ゲーム N のうち、二人が最適に行動したとき Alice が勝つゲームは何個あるか求めてください。
制約
- 1 \leq N ,A,B \leq 10^{18}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A B
出力
答えを出力せよ。
入力例 1
4 2 1
出力例 1
2
ゲーム 1 では、Alice は操作を行えないため Alice の負けとなります。
ゲーム 2 では、Alice が石を 2 個取ることで Bob は操作を行えなくなり、Alice の勝ちとなります。
ゲーム 3 では、Alice が石を 2 個取り、Bob が石を 1 個取るとAlice は操作を行えないため Alice の負けとなります。
ゲーム 4 では、Alice が石を 2 \times 2 = 4 個取ることで Bob は操作を行えなくなり、Alice の勝ちとなります。
以上より、ゲーム 1,2,3,4 のうちAlice が勝つゲームは 2 個です。
入力例 2
27182818284 59045 23356
出力例 2
10752495144
Score : 500 points
Problem Statement
The following game is called Game n:
The game is played by Alice and Bob. Initially, there are n stones.
The players alternate turns, making a move described below, with Alice going first. The player who becomes unable to make a move loses.
- In Alice's turn, she must remove a number of stones that is a positive multiple of A.
- In Bob's turn, he must remove a number of stones that is a positive multiple of B.
In how many of Game 1, Game 2, ..., Game N does Alice win when both players play optimally?
Constraints
- 1 \leq N ,A,B \leq 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A B
Output
Print the answer.
Sample Input 1
4 2 1
Sample Output 1
2
In Game 1, Alice cannot make a move and thus loses.
In Game 2, Alice removes 2 stones, and then Bob cannot make a move: Alice wins.
In Game 3, Alice removes 2 stones, Bob removes 1 stone, and then Alice cannot make a move and loses.
In Game 4, Alice removes 2 \times 2 = 4 stones, and then Bob cannot make a move: Alice wins.
Therefore, Alice wins in two of the four games.
Sample Input 2
27182818284 59045 23356
Sample Output 2
10752495144
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
(1,2,\ldots,2N) の順列 P=(P_1,P_2,\ldots,P_{2N}) に対し、スコアを以下で定義します。
P を順序を保ったまま二つの長さ N の(連続するとは限らない)部分列 A = (A_1,A_2,\ldots,A_N),B = (B_1,B_2,\ldots,B_N) に分割する。分割を行ったときに得られる \displaystyle\sum_{i=1}^{N}A_i B_i の最大値をスコアとする。
(1,2,\ldots,2N) の順列全てについてスコアを計算し、それらの最大値を M とします。 (1,2,\ldots,2N) の順列のうち、スコアが M であるものの個数を 998244353 で割ったあまりを求めてください。
制約
- 1 \leq N \leq 2\times 10^5
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
2
出力例 1
16
考えられる順列 24 通りの中で、スコアの最大値 M は 14 です。スコアが 14 となる順列は 16 通りあります。
例えば、順列 (1,2,3,4) は A=(1,3), B=(2,4) と分割することで、\sum _{i=1}^{N}A_i B_i = 14 となります。
入力例 2
10000
出力例 2
391163238
998244353 で割ったあまりを答えてください。
Score : 600 points
Problem Statement
The score of a permutation P=(P_1,P_2,\ldots,P_{2N}) of (1,2,\ldots,2N) is defined as follows:
Consider dividing P into two (not necessarily contiguous) subsequences A = (A_1,A_2,\ldots,A_N) and B = (B_1,B_2,\ldots,B_N). The score of P is the maximum possible value of \displaystyle\sum_{i=1}^{N}A_i B_i in such a division.
Let M be the maximum among the scores of all permutations of (1,2,\ldots,2N). Find the number, modulo 998244353, of permutations of (1,2,\ldots,2N) with the score of M.
Constraints
- 1 \leq N \leq 2\times 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
2
Sample Output 1
16
The maximum among the scores of the 24 possible permutations, M, is 14, and there are 16 permutations with the score of 14.
For instance, the permutation (1,2,3,4) achieves \sum _{i=1}^{N}A_i B_i = 14 in the division A=(1,3), B=(2,4).
Sample Input 2
10000
Sample Output 2
391163238
Print the count modulo 998244353.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
以下の条件を全て満たす整数集合 S を一つ構築してください。なお、この問題の制約下で条件を満たす S が少なくとも一つ存在することが証明できます。
- S の要素数は N
- S の要素は -10^7 以上 10^7 以下の相異なる整数
- \displaystyle \sum _{s \in S} s = M
- S の任意の相異なる要素 x,y,z (x < y < z) について y-x\neq z-y
制約
- 1 \leq N \leq 10^4
- |M| \leq N\times 10^6
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
S の要素を s_1,s_2,\ldots,s_N とする。条件を満たす S を 1 つ以下の形式で出力せよ。
s_1 s_2 \ldots s_N
条件を満たす解が複数存在する場合、どれを出力しても正解とみなされる。
入力例 1
3 9
出力例 1
1 2 6
2-1 \neq 6-2 であり、 1+2+6=9 なのでこの出力は条件を満たします。他にも様々な答えが考えられます。
入力例 2
5 -15
出力例 2
-15 -5 0 2 3
M が負のこともあります。
Score : 700 points
Problem Statement
Construct a set S of integers satisfying all of the conditions below. It can be proved that at least one such set S exists under the Constraints of this problem.
- S has exactly N elements.
- The element of S are distinct integers between -10^7 and 10^7 (inclusive).
- \displaystyle \sum _{s \in S} s = M.
- y-x\neq z-y for every triple x,y,z (x < y < z) of distinct elements in S.
Constraints
- 1 \leq N \leq 10^4
- |M| \leq N\times 10^6
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M
Output
Let s_1,s_2,\ldots,s_N be the elements of S. Print a set S that satisfies the conditions in the following format:
s_1 s_2 \ldots s_N
If multiple solutions exist, any of them will be accepted.
Sample Input 1
3 9
Sample Output 1
1 2 6
We have 2-1 \neq 6-2 and 1+2+6=9, so this output satisfies the conditions. Many other solutions exist.
Sample Input 2
5 -15
Sample Output 2
-15 -5 0 2 3
M may be negative.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
長さ N の非負整数列 A=(A_1,A_2,\ldots,A_{N}),B=(B_1,B_2,\ldots,B_{N}) が与えられます。
数列 A に対し以下の操作を 70000 回以下行うことで A を B に一致させられるか判定し、可能な場合は実際に操作手順を一つ示してください。
- 整数 K\ (1\le K \le N) を選ぶ。全ての i\ (2\leq i \leq K) について、 A_i の値を A_{i-1} \oplus A_i で置き換える。この置き換えは全ての i\ (2\leq i \leq K) に対して同時に行う。
ただしここで、\oplus はビット単位 \mathrm{XOR} 演算を表します。
ビット単位 \mathrm{XOR} 演算とは
非負整数 A,B のビット単位 \mathrm{XOR} 演算、A\oplus B は、以下のように定義されます。
- A\oplus B を二進表記した際の 2^k\ (k\geq 0) の位の数は、A,B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
例えば、3\oplus 5 = 6 となります(二進表記すると: 011\oplus 101 = 110)。
制約
- 2 \leq N \leq 1000
- 0 \leq A_i, B_i < 2^{60}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
出力
70000 回以下の操作で A を B に一致させられない場合、No
と出力せよ。一致させられる場合、操作回数を M 回とし、i 回目の操作で選んだ整数を K_i として以下の形式で出力せよ。
Yes M K_1 K_2 \ldots K_M
条件を満たす解が複数存在する場合、どれを出力しても正解とみなされる。
入力例 1
3 1 2 0 1 2 3
出力例 1
Yes 2 2 3
この出力例では、操作によって数列 A は以下のように変化します。
- 初期状態:A=(1, 2, 0)
- 1 回目の操作後:A=(1, 3, 0)
- 2 回目の操作後:A=(1, 2, 3)
2 回の操作後、A と B は一致しているのでこの出力は条件を満たします。
入力例 2
2 10 100 1 0
出力例 2
No
入力例 3
2 1152921504606846975 0 1152921504606846975 0
出力例 3
Yes 0
Score : 800 points
Problem Statement
You are given two sequences, each of length N, consisting of non-negative integers: A=(A_1,A_2,\ldots,A_{N}) and B=(B_1,B_2,\ldots,B_{N}).
Determine whether it is possible to make A equal to B by performing the operation below at most 70000 times. If it is possible, present a specific sequence of operations that achieves it.
- Choose an integer K\ (1\le K \le N). For every integer i\ (2\leq i \leq K), simultaneously replace the value of A_i with A_{i-1} \oplus A_i.
Here, \oplus denotes bitwise \mathrm{XOR}.
What is bitwise \mathrm{XOR}?
The bitwise \mathrm{XOR} of non-negative integers A and B, A\oplus B, is defined as follows:
- When A\oplus B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of the digits in that place of A and B are 1, and 0 otherwise.
For example, 3\oplus 5 = 6 (in base two: 011\oplus 101 = 110).
Constraints
- 2 \leq N \leq 1000
- 0 \leq A_i, B_i < 2^{60}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
Output
If it is impossible to make A equal to B in at most 70000 operations, print No
. If it is possible, print a sequence of operations that achieves it in the following format, where M is the number of operations, and K_i is the integer chosen in the i-th operation:
Yes M K_1 K_2 \ldots K_M
If multiple solutions exist, any of them will be accepted.
Sample Input 1
3 1 2 0 1 2 3
Sample Output 1
Yes 2 2 3
In this output, the sequence A is changed as follows:
- Initially: A=(1, 2, 0).
- After the 1-st operation: A=(1, 3, 0).
- After the 2-nd operation: A=(1, 2, 3).
After the two operations, A and B are equal, achieving the objective.
Sample Input 2
2 10 100 1 0
Sample Output 2
No
Sample Input 3
2 1152921504606846975 0 1152921504606846975 0
Sample Output 3
Yes 0
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 1200 点
問題文
0 以上 M 以下の整数からなる長さ N の広義単調増加列 A=(A_1,A_2,\ldots,A_N) のうち、以下を満たすものの個数を 998244353 で割ったあまりを各 K=0,1,\ldots,\mathrm{MOD}-1 に対して求めてください。
- A の要素の総和を \mathrm{MOD} で割ったあまりが K に等しい。
広義単調増加列とは
ある数列 B について、 B の長さを |B| としたとき、全ての整数 i (1 \le i \le |B| - 1) について、 B_i \leq B_{i+1} が成り立つとき、またそのときに限って、 B は広義単調増加列です。制約
- 1 \leq N ,M\leq 10^6
- 1\leq \mathrm{MOD}\leq 500
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M \mathrm{MOD}
出力
各 K=0,1,\ldots,\mathrm{MOD}-1 に対して、条件を満たす数列の個数を 998244353 で割ったあまりを出力せよ。
入力例 1
2 2 4
出力例 1
2 1 2 1
0 以上 2 以下の整数からなる長さ 2 の広義単調増加列は (0, 0), (0, 1),(0,2), (1,1),(1,2),(2,2) の 6 通りです。
-
総和を 4 で割ったあまりが 0 のもの:(0,0),(2,2) の 2 通り
-
総和を 4 で割ったあまりが 1 のもの:(0,1) の 1 通り
-
総和を 4 で割ったあまりが 2 のもの:(0,2),(1,1) の 2 通り
-
総和を 4 で割ったあまりが 3 のもの:(1,2) の 1 通り
です。
入力例 2
3 45 3
出力例 2
5776 5760 5760
入力例 3
1000000 1000000 6
出力例 3
340418986 783857865 191848859 783857865 340418986 635287738
998244353 で割ったあまりを答えてください。
Score : 1200 points
Problem Statement
Find the number, modulo 998244353, of non-decreasing sequences A=(A_1,A_2,\ldots,A_N) of length N consisting of integers between 0 and M (inclusive) that satisfy the following, for each K=0,1,\ldots,\mathrm{MOD}-1:
- the sum of the elements in A is congruent to K modulo \mathrm{MOD}.
What is a non-decreasing sequence?
A sequence B is non-decreasing if and only if B_i \leq B_{i+1} for every integer (1 \le i \le |B| - 1), where |B| is the length of B.Constraints
- 1 \leq N ,M\leq 10^6
- 1\leq \mathrm{MOD}\leq 500
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M \mathrm{MOD}
Output
For each K=0,1,\ldots,\mathrm{MOD}-1, print the number, modulo 998244353, of sequences that satisfy the condition.
Sample Input 1
2 2 4
Sample Output 1
2 1 2 1
There are 6 non-decreasing sequences of length 2 consisting of integers between 0 and 2: (0, 0), (0, 1),(0,2), (1,1),(1,2),(2,2). Here, we have:
-
2 sequences whose sums are congruent to 0 modulo 4: (0,0),(2,2);
-
1 sequence whose sum is congruent to 1 modulo 4: (0,1);
-
2 sequences whose sums are congruent to 2 modulo 4: (0,2),(1,1);
-
1 sequence whose sum is congruent to 3 modulo 4: (1,2).
Sample Input 2
3 45 3
Sample Output 2
5776 5760 5760
Sample Input 3
1000000 1000000 6
Sample Output 3
340418986 783857865 191848859 783857865 340418986 635287738
Print the counts modulo 998244353.