AtCoder Grand Contest 063

A - Mex Game

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

A, B からなる長さ N+1 の文字列 S = S_0\cdots S_N が与えられます．各 k=1, \ldots, N に対して次の問題を解いてください：

Alice と Bob が集合 X を使ってゲームをします．X ははじめ空集合で，t=1,\ldots, k の順に次の行動を行います．

t が奇数ならば，Alice が非負整数 x を選び，X を X\cup \{x\} に置き換える．

t が偶数ならば，Bob が非負整数 x を選び，X を X\cup \{x\} に置き換える．

k 回すべての行動が終わった時点での \mathrm{mex}(X) を x とするとき，文字 S_x が A ならば Alice が，S_x が B ならば Bob が勝者となります．集合 X の要素数は k 以下であるため，x = \mathrm{mex}(X) \leq k が成り立つ（したがって文字 S_x が存在する）ことに注意してください．

両者が最適に行動した場合の勝者の名前を出力してください．

\mathrm{mex}(X) とは？

非負整数からなる有限集合 X に対し，x\notin X を満たす最小の非負整数 x を \mathrm{mex}(X) と定義します．

制約

1\leq N\leq 2\times 10^5
S は A, B からなる長さ N+1 の文字列である．

入力

入力は以下の形式で標準入力から与えられます．

N
S

出力

N 行出力してください．i 行目には，k=i とした場合のゲームについて，両者が最適に行動した場合の勝者の名前（Alice または Bob）を出力してください．

入力例 1

2
ABB

出力例 1

Alice
Bob

k=1 とした場合のゲームの進行例の一例を次に示します．

Alice が x=10 を選ぶ．
\mathrm{mex}(X)=\mathrm{mex}(\lbrace 10\rbrace) = 0 であり，S_0 は A なので，Alice が勝利する．

k=2 とした場合のゲームの進行例の一例を次に示します．

Alice が x=2 を選ぶ．
Bob が x=0 を選ぶ．
\mathrm{mex}(X)=\mathrm{mex}(\lbrace 0,2\rbrace) = 1 であり，S_1 は B なので，Bob が勝利する．

入力例 2

4
AAAAA

出力例 2

Alice
Alice
Alice
Alice

入力例 3

7
BBAABABA

出力例 3

Bob
Bob
Alice
Bob
Alice
Bob
Alice

Score : 300 points

Problem Statement

You are given a string of length N+1 consisting of A and B: S = S_0\cdots S_N. For each k=1, \ldots, N, solve the following problem.

Alice and Bob will play a game using a set X, which is initially empty. For t=1,\ldots, k in this order, they will do the following action:

if t is odd, Alice will choose a non-negative integer x and replace X with X\cup \{x\};

if t is even, Bob will choose a non-negative integer x and replace X with X\cup \{x\}.

Let x be \mathrm{mex}(X) after all k actions. If the character S_x is A, Alice wins; if S_x is B, Bob wins. Note that X has at most k elements, so x = \mathrm{mex}(X) \leq k and the character S_x exists.

Print the name of the winner when both players play optimally.

What is \mathrm{mex}(X)?

For a finite set X consisting of non-negative integers, \mathrm{mex}(X) is the smallest non-negative integer x such that x\notin X.

Constraints

1\leq N\leq 2\times 10^5
S is a string of length N+1 consisting of A and B.

Input

The input is given from Standard Input in the following format:

N
S

Output

Print N lines. The i-th line should contain the winner's name (Alice or Bob) when both players play optimally in the game with k=i.

Sample Input 1

2
ABB

Sample Output 1

Alice
Bob

Here is a possible progression of the game with k=1.

Alice chooses x=10.
\mathrm{mex}(X)=\mathrm{mex}(\lbrace 10\rbrace) = 0, and S_0 is A, so Alice wins.

Here is a possible progression of the game with k=2.

Alice chooses x=2.
Bob chooses x=0.
\mathrm{mex}(X)=\mathrm{mex}(\lbrace 0,2\rbrace) = 1, and S_1 is B, so Bob wins.

Sample Input 2

4
AAAAA

Sample Output 2

Alice
Alice
Alice
Alice

Sample Input 3

7
BBAABABA

Sample Output 3

Bob
Bob
Alice
Bob
Alice
Bob
Alice

B - Insert 1, 2, 3, ...

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

正整数からなる数列 a = (a_1, \ldots, a_n) が生成可能であるとは，空列からはじめて次の操作の繰り返しで a が得られることをいいます．

操作：正整数 k を選び，列の好きな位置に (1, 2, \ldots, k-1, k) を挿入する．より形式的には，列 a = (a_1, \ldots, a_m) に対して 0\leq i\leq m となる整数 i および正整数 k を選び，a を (a_1,\ldots,a_{i}, 1, 2, \ldots, k-1, k, a_{i+1}, \ldots, a_m) に置き換える．

例えば a = (1,2,1,1,2,1,3,4,2,3) は生成可能です．次が生成手順の一例です：

() \to (\boldsymbol{1,2}) \to (1,2,\boldsymbol{1,2,3}) \to (1,2,1,\boldsymbol{1,2,3,4},2,3) \to (1,2,1,1,2,\boldsymbol{1},3,4,2,3)

正整数からなる数列 A = (A_1, \ldots, A_N) が与えられます．次を満たす整数の組 (L, R) の個数を求めてください：

1\leq L\leq R\leq N であり，連続部分列 (A_L, \ldots, A_R) は生成可能である．

制約

1\leq N\leq 5\times 10^5
1\leq A_i\leq N

入力

入力は以下の形式で標準入力から与えられます．

N
A_1 \ldots A_N

出力

条件を満たす整数の組 (L, R) の個数を出力してください．

入力例 1

6
1 2 1 2 1 3

出力例 1

次の 11 個です：

(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (3,3), (3,4), (3,5), (3,6), (5,5)

入力例 2

5
1 1 1 1 1

出力例 2

すべての連続部分列が生成可能です．

入力例 3

7
1 2 1 2 1 3 4

出力例 3

Score : 600 points

Problem Statement

A sequence a = (a_1, \ldots, a_n) consisting of positive integers is said to be generatable when one can obtain a by repeating the following operation on an empty sequence.

Operation: Choose a positive integer k, and insert (1, 2, \ldots, k-1, k) into some position in the sequence. More formally, for a sequence a = (a_1, \ldots, a_m), choose an integer i such that 0\leq i\leq m and a positive integer k, and replace a with (a_1,\ldots,a_{i}, 1, 2, \ldots, k-1, k, a_{i+1}, \ldots, a_m).

For instance, a = (1,2,1,1,2,1,3,4,2,3) is generatable. Here is one way to generate it:

() \to (\boldsymbol{1,2}) \to (1,2,\boldsymbol{1,2,3}) \to (1,2,1,\boldsymbol{1,2,3,4},2,3) \to (1,2,1,1,2,\boldsymbol{1},3,4,2,3).

You are given a sequence A = (A_1, \ldots, A_N) consisting of positive integers. Find the number of pairs of integers (L, R) such that:

1\leq L\leq R\leq N and the contiguous subsequence (A_L, \ldots, A_R) is generatable.

Constraints

1\leq N\leq 5\times 10^5
1\leq A_i\leq N

Input

The input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

Print the number of pairs of integers (L, R) satisfying the conditions.

Sample Input 1

6
1 2 1 2 1 3

Sample Output 1

Here are the 11 sought pairs:

(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (3,3), (3,4), (3,5), (3,6), (5,5).

Sample Input 2

5
1 1 1 1 1

Sample Output 2

All the contiguous subsequences are generatable.

Sample Input 3

7
1 2 1 2 1 3 4

Sample Output 3

C - Add Mod Operations

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

非負整数列 A = (A_1, \ldots, A_N) および B=(B_1, \ldots, B_N) が与えられます．

以下の操作を 0 回以上 N 回以下行うことで，A を B に一致させることができるか否かを判定してください．

操作：0\leq x < y\leq 10^{18} を満たす整数 x,y を選ぶ．すべての i に対して，A_i を (A_i+x)\bmod y に置き換える．

A を B に一致させることが可能な場合には，そのような手順をひとつ出力してください．

制約

1\leq N\leq 1000
0\leq A_i\leq 10^9
0\leq B_i\leq 10^9

入力

入力は以下の形式で標準入力から与えられます．

N
A_1 \ldots A_N
B_1 \ldots B_N

出力

0 回以上 N 回以下の操作で A を B に一致させることが不可能な場合には，No と出力してください．

No

可能な場合には，操作手順を次の形式で出力してください．

Yes
K
x_1 y_1
\vdots
x_K y_K

ここで K は操作回数で，x_i, y_i は i 回目の操作で選ぶ整数 x,y を表します．これらは次を満たす必要があります．

0\leq K\leq N
0\leq x_i < y_i \leq 10^{18}

条件を満たす操作手順が複数存在する場合には，そのどれを出力しても正解と見なされます．

入力例 1

4
7 2 4 5
3 3 5 0

出力例 1

Yes
2
3 5
3 6

次のようにして A を B に一致させることができます．

はじめ A = (7,2,4,5) です．
(x,y) = (3,5) として操作を行うと，A = (0,0,2,3) になります．
(x,y) = (3,6) として操作を行うと，A = (3,3,5,0) になります．

入力例 2

1
5
3

出力例 2

Yes
1
2 4

入力例 3

2
3 1
3 1

出力例 3

Yes
0

入力例 4

2
0 0
1 2

出力例 4

No

Score : 800 points

Problem Statement

You are given sequences of non-negative integers: A = (A_1, \ldots, A_N) and B=(B_1, \ldots, B_N).

Determine whether one can make A equal B by performing the following operation between 0 and N times, inclusive.

Operation: Choose integers x,y such that 0\leq x < y\leq 10^{18}. For every i, replace A_i with (A_i+x)\bmod y.

If one can make A equal B, print one way to do so.

Constraints

1\leq N\leq 1000
0\leq A_i\leq 10^9
0\leq B_i\leq 10^9

Input

The input is given from Standard Input in the following format:

N
A_1 \ldots A_N
B_1 \ldots B_N

Output

If one cannot make A equal B by performing the operation between 0 and N times, inclusive, print No.

No

If one can do so, print one way in the following format:

Yes
K
x_1 y_1
\vdots
x_K y_K

Here, K is the number of operations, and x_i, y_i are integers x, y chosen in the i-th operation. These must satisfy the following:

0\leq K\leq N
0\leq x_i < y_i \leq 10^{18}

If there are multiple ways to achieve the objective, you may print any of them.

Sample Input 1

4
7 2 4 5
3 3 5 0

Sample Output 1

Yes
2
3 5
3 6

One can make A equal B as follows.

Initially, A = (7,2,4,5).
The operation with (x,y) = (3,5) makes A = (0,0,2,3).
The operation with (x,y) = (3,6) makes A = (3,3,5,0).

Sample Input 2

1
5
3

Sample Output 2

Yes
1
2 4

Sample Input 3

2
3 1
3 1

Sample Output 3

Yes
0

Sample Input 4

2
0 0
1 2

Sample Output 4

No

D - Many CRT

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1200 点

問題文

正整数 N, a, b, c, d が与えられます．

k=0,1,\ldots,N-1 すべてに対して x\equiv a+kb \pmod{c+kd} が成り立つような非負整数 x が存在するか否かを判定してください．存在する場合には，そのような x のうち最小のものを 998244353 で割った余りを求めてください．

制約

2\leq N\leq 10^6
1\leq a,b,c,d\leq 10^6

入力

入力は以下の形式で標準入力から与えられます．

N a b c d

出力

条件を満たす非負整数 x が存在しない場合には -1 を出力してください．存在する場合には，そのような x のうち最小のものを 998244353 で割った余りを出力してください．

入力例 1

2 1 2 3 4

出力例 1

x\equiv 1\pmod{3} かつ x\equiv 3\pmod{7} を満たす最小の非負整数は x=10 です．

入力例 2

2 1 1 10 10

出力例 2

-1

x\equiv 1\pmod{10} かつ x\equiv 2\pmod{20} を満たす非負整数は存在しません．

入力例 3

100 20 30 2 3

出力例 3

条件を満たす最小の非負整数は x= 0 です．

入力例 4

9 12 34 56 78

出力例 4

827501367

条件を満たす最小の非負整数は x= 15977769171609124 です．

Score : 1200 points

Problem Statement

You are given positive integers N, a, b, c, d.

Determine whether there is a non-negative integer x such that x\equiv a+kb \pmod{c+kd} for every k=0,1,\ldots,N-1. If it exists, find the smallest such x modulo 998244353.

Constraints

2\leq N\leq 10^6
1\leq a,b,c,d\leq 10^6

Input

The input is given from Standard Input in the following format:

N a b c d

Output

If there is no non-negative integer x satisfying the condition, print -1. Otherwise, print the smallest such x modulo 998244353.

Sample Input 1

2 1 2 3 4

Sample Output 1

x=10 is the smallest non-negative integer such that x\equiv 1\pmod{3} and x\equiv 3\pmod{7}.

Sample Input 2

2 1 1 10 10

Sample Output 2

-1

No non-negative integer x satisfies x\equiv 1\pmod{10} and x\equiv 2\pmod{20}.

Sample Input 3

100 20 30 2 3

Sample Output 3

x= 0 is the smallest non-negative integer satisfying the condition.

Sample Input 4

9 12 34 56 78

Sample Output 4

827501367

x=15977769171609124 is the smallest non-negative integer satisfying the condition.

E - Child to Parent

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 1400 点

問題文

頂点に 1 から N の番号がついた N 頂点の根付き木があります．頂点 1 が根であり，頂点 i (2\leq i\leq N) の親は P_i です．

非負整数 r および非負整数列 A = (A_1, \ldots, A_N) が与えられます．あなたはこの数列に対して，次の操作を何度でも行うことができます（0 回でもよい）：

i\geq 2 かつ A_i \geq 1 となる i をひとつ選ぶ．A_i を A_i - 1 に，A_{P_i} を A_{P_i}+r に置き換える．

最終的な非負整数列 A としてありうるものの個数を 998244353 で割った余りを求めてください．

制約

2\leq N\leq 300
1\leq P_i \leq i - 1 (2\leq i\leq N)
0\leq r \leq 10^9
0\leq A_i \leq 10^9

入力

入力は以下の形式で標準入力から与えられます．

N
P_2 \ldots P_N
r
A_1 \ldots A_N

出力

最終的な非負整数列 A としてありうるものの個数を 998244353 で割った余りを出力してください．

入力例 1

出力例 1

最終的な A としてありうるのは次の 4 個です：(1,1,1), (3,0,1), (3,1,0), (5,0,0)．

入力例 2

出力例 2

最終的な A としてありうるのは次の 5 個です：(1,1,1), (1,2,0), (2,0,1), (2,1,0), (3,0,0)．

入力例 3

出力例 3

最終的な A としてありうるのは次の 6 個です：(1,1,1), (1,3,0), (3,0,1), (3,2,0), (5,1,0), (7,0,0)．

入力例 4

出力例 4

入力例 5

出力例 5

87782255

Score : 1400 points

Problem Statement

There is a rooted tree with N vertices numbered 1 to N. Vertex 1 is the root, and the parent of vertex i (2\leq i\leq N) is P_i.

You are given a non-negative integer r and a sequence of non-negative integers A = (A_1, \ldots, A_N). You can perform the following operation on the sequence any number of times, possibly zero.

Choose an i such that i\geq 2 and A_i \geq 1. Replace A_i with A_i - 1 and A_{P_i} with A_{P_i}+r.

Find the number, modulo 998244353, of possible final states of the sequence A.

Constraints

2\leq N\leq 300
1\leq P_i \leq i - 1 (2\leq i\leq N)
0\leq r \leq 10^9
0\leq A_i \leq 10^9

Input

The input is given from Standard Input in the following format:

N
P_2 \ldots P_N
r
A_1 \ldots A_N

Output

Print the number, modulo 998244353, of possible final states of the sequence A.

Sample Input 1

Sample Output 1

The four possible final states of A are (1,1,1), (3,0,1), (3,1,0), and (5,0,0).

Sample Input 2

Sample Output 2

The five possible final states of A are (1,1,1), (1,2,0), (2,0,1), (2,1,0), and (3,0,0).

Sample Input 3

Sample Output 3

The six possible final states of A are (1,1,1), (1,3,0), (3,0,1), (3,2,0), (5,1,0), and (7,0,0).

Sample Input 4

Sample Output 4

Sample Input 5

Sample Output 5

87782255

F - Simultaneous Floor

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 1700 点

問題文

非負整数の組 a = (a_1,a_2), b = (b_1,b_2) が与えられます．あなたは組 a に対して次の操作を何度でも行うことができます（0 回でもよい）：

操作：正実数 x をひとつ選ぶ．a = (a_1,a_2) を (\lfloor a_1x\rfloor, \lfloor a_2x\rfloor) に置き換える．

あなたの目的は，組 a と組 b を等しくすることです．目的を達成することが可能か否かを判定してください．目的を達成することが可能な場合には，そのために必要な操作回数の最小値を求めてください．

T 個のテストケースが与えられるので，それぞれについて答えを求めてください．

制約

1\leq T\leq 10^5
0\leq a_1, a_2, b_1, b_2 \leq 10^9

入力

入力は以下の形式で標準入力から与えられます．

T
\text{case}_1
\vdots
\text{case}_T

各テストケースは以下の形式で与えられます．

a_1 a_2 b_1 b_2

出力

T 行出力してください．i 行目には i 番目のテストケースについて，a を b に等しくすることが不可能ならば -1，可能ならばそのために必要な操作回数の最小値を出力してください．

入力例 1

7
2 3 1 1
1 1 2 3
3 2 9 8
12 34 56 78
56 78 12 34
87 65 43 21
43 21 87 65

出力例 1

1 番目のテストケースについて，以下が最適な手順の一例です：

はじめ，a = (2,3) である．
x = 0.6 として操作を行う．a は (\lfloor 1.2 \rfloor, \lfloor 1.8\rfloor) = (1,1) に置き換えられる．

3 番目のテストケースについて，以下が最適な手順の一例です：

はじめ，a = (3,2) である．
x = 1.5 として操作を行う．a は (4,3) に置き換えられる．
x = 1.7 として操作を行う．a は (6,5) に置き換えられる．
x = 1.6 として操作を行う．a は (9,8) に置き換えられる．

入力例 2

出力例 2

Score : 1700 points

Problem Statement

You are given pairs of non-negative integers a = (a_1,a_2) and b = (b_1,b_2). You can perform the following operation on the pair a any number of times, possibly zero.

Operation: Choose a positive real number x. Replace a = (a_1,a_2) with (\lfloor a_1x\rfloor, \lfloor a_2x\rfloor).

Your objective is to make the pair a equal the pair b. Determine whether it is achievable. If it is, find the minimum number of times you must perform the operation to achieve it.

You have T test cases to solve.

Constraints

1\leq T\leq 10^5
0\leq a_1, a_2, b_1, b_2 \leq 10^9

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:

a_1 a_2 b_1 b_2

Output

Print T lines. The i-th line should contain -1 if it is impossible to make a equal b in the i-th test case, and otherwise, the minimum number of times the operation must be performed to achieve the objective.

Sample Input 1

7
2 3 1 1
1 1 2 3
3 2 9 8
12 34 56 78
56 78 12 34
87 65 43 21
43 21 87 65

Sample Output 1

For the first test case, here is one optimal solution.

Initially, a = (2,3).
Perform the operation with x = 0.6, replacing a with (\lfloor 1.2 \rfloor, \lfloor 1.8\rfloor) = (1,1).

For the third test case, here is one optimal solution.

Initially, a = (3,2).
Perform the operation with x = 1.5, replacing a with (4,3).
Perform the operation with x = 1.7, replacing a with (6,5).
Perform the operation with x = 1.6, replacing a with (9,8).

Sample Input 2

Sample Output 2