AtCoder Regular Contest 155

A - ST and TS Palindrome

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

英小文字からなる長さ N の文字列 S と正整数 K が与えられます。

以下の条件を満たす長さ K の文字列 S' が存在するか判定してください。

S, S' をこの順に結合して得られる文字列は回文である
S', S をこの順に結合して得られる文字列は回文である

T 個のテストケースが与えられるのでそれぞれについて判定してください。

制約

1 \leq T \leq 10^5
1 \leq N \leq 2 \times 10^5
1 \leq K \leq 10^{18}
S は英小文字からなる長さ N の文字列
入力される数値はすべて整数
1 つの入力に含まれるテストケースについて、 N の総和は 2 \times 10^5 以下

入力

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

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

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

N K
S

出力

T 行出力せよ。i 行目には i 番目のテストケースについて、条件を満たす文字列 S' が存在する場合は Yes を、存在しない場合は No を出力せよ。

入力例 1

2
6 2
abbaab
5 3
abcbb

出力例 1

Yes
No

1 番目のテストケースについて、例えば S' = {}ba とすると S,S' をこの順に結合して得られる文字列 abbaabba は回文になっています。また、 S',S をこの順に結合して得られる文字列 baabbaab も回文になっています。以上より S' = {}ba は条件を満たすので答えは Yes になります。

2 番目のテストケースについては、条件を満たす S' が存在しないことが証明できます。

入力例 2

3
12 400378271514996652
njvhhvjnnjvh
10 884633988115575508
rrhiyvrrur
36 71630165869626180
vsxmxajrrduhhudrrjaxmxsvvsxmxajrrduh

出力例 2

Yes
No
Yes

Score : 400 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters, and a positive integer K.

Determine whether there is a string S' of length K that satisfies the following conditions.

The concatenation of S and S' in this order is a palindrome.
The concatenation of S' and S in this order is a palindrome.

You have T test cases to solve.

Constraints

1 \leq T \leq 10^5
1 \leq N \leq 2 \times 10^5
1 \leq K \leq 10^{18}
S is a string of length N consisting of lowercase English letters.
All numbers in the input are integers.
In each input file, the sum of N over the test cases is at most 2 \times 10^5.

Input

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

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

Each case is in the following format:

N K
S

Output

Print T lines. The i-th line should contain Yes if there is a string S' that satisfies the conditions for the i-th test case, and No otherwise.

Sample Input 1

2
6 2
abbaab
5 3
abcbb

Sample Output 1

Yes
No

For the first test case, if we let S' = {}ba, for instance, the concatenation of S and S' in this order will be abbaabba, which is a palindrome. Here, the concatenation of S' and S in this order is baabbaab, which is also a palindrome. Thus, S' = {}ba satisfies the condition, so the answer is Yes.

For the second test case, we can prove that no string satisfies the conditions.

Sample Input 2

3
12 400378271514996652
njvhhvjnnjvh
10 884633988115575508
rrhiyvrrur
36 71630165869626180
vsxmxajrrduhhudrrjaxmxsvvsxmxajrrduh

Sample Output 2

Yes
No
Yes

B - Abs Abs Function

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

2 つの非負整数からなる組の集合 S 、および非負整数 x に対し f_S(x) を \displaystyle f_S(x)=\min_{(a, b) \in S} \left| \left| x-a \right| - b \right| と定義します。

2 つの非負整数からなる組の集合 T があります。はじめ T=\lbrace (A, B)\rbrace です。

Q 個のクエリを処理してください。i 番目のクエリでは 3 つの非負整数 t_i, a_i, b_i が与えられるので、以下のように処理してください。

t_i=1 のとき、 T に 2 つの非負整数からなる組 (a_i, b_i) を追加する。
t_i=2 のとき、 a_i \leq x \leq b_i を満たす非負整数 x に対する f_{T}(x) の最小値を出力する。

制約

1 \leq Q \leq 2 \times 10^5
0 \leq A,B \leq 10^{9}
t_i は 1 または 2
0 \leq a_i,b_i \leq 10^{9}
t_i=2 のとき、a_i \leq b_i
t_i=2 を満たすクエリは 1 つ以上存在する
入力される値はすべて整数

入力

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

Q A B
t_1 a_1 b_1
t_2 a_2 b_2
\vdots
t_Q a_Q b_Q

出力

t_i=2 であるような各クエリについて、答えを 1 行に 1 つずつ、順に出力せよ。

入力例 1

出力例 1

2
1

4 番目のクエリを実行するとき、 T=\lbrace(0, 5), (3, 11), (8, 2) \rbrace です。8 \leq x \leq 9 において f_T(x) は x=9 で最小値 f_T(9)=1 をとります。

入力例 2

2 1 2
1 2 3
2 2 6

出力例 2

入力例 3

20 795629912 123625148
2 860243184 892786970
2 645778367 668513124
1 531411849 174630323
1 635062977 195695960
2 382061637 411843651
1 585964296 589553566
1 310118888 68936560
1 525351160 858166280
2 395304415 429823333
2 583145399 703645715
2 97768492 218377432
1 707220749 459967102
1 210842017 363390878
2 489541834 553583525
2 731279777 811513313
1 549864943 493384741
1 815378318 826084592
2 369622093 374205455
1 78240781 821999998
2 241667193 243982581

出力例 3

Score : 500 points

Problem Statement

For a set S of pairs of non-negative integers, and a non-negative integer x, let f_S(x) defined as \displaystyle f_S(x)=\min_{(a, b) \in S} \left| \left| x-a \right| - b \right|.

We have a set T of pairs of non-negative integers. Initially, T=\lbrace (A, B)\rbrace.

Process Q queries. The i-th query gives you three non-negative integers t_i, a_i, and b_i, and asks you to do the following.

If t_i=1, add to T the pair (a_i, b_i) of non-negative integers.
If t_i=2, print the minimum value of f_{T}(x) for a non-negative integer x such that a_i \leq x \leq b_i.

Constraints

1 \leq Q \leq 2 \times 10^5
0 \leq A,B \leq 10^{9}
t_i is 1 or 2.
0 \leq a_i,b_i \leq 10^{9}
If t_i=2, then a_i \leq b_i.
There is at least one query with t_i=2.
All values in the input are integers.

Input

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

Q A B
t_1 a_1 b_1
t_2 a_2 b_2
\vdots
t_Q a_Q b_Q

Output

For each query with t_i=2 in the given order, print the answer in its own line.

Sample Input 1

Sample Output 1

2
1

In the fourth query, T=\lbrace(0, 5), (3, 11), (8, 2) \rbrace. In 8 \leq x \leq 9, f_T(x) takes the minimum value f_T(9)=1 at x=9.

Sample Input 2

2 1 2
1 2 3
2 2 6

Sample Output 2

Sample Input 3

20 795629912 123625148
2 860243184 892786970
2 645778367 668513124
1 531411849 174630323
1 635062977 195695960
2 382061637 411843651
1 585964296 589553566
1 310118888 68936560
1 525351160 858166280
2 395304415 429823333
2 583145399 703645715
2 97768492 218377432
1 707220749 459967102
1 210842017 363390878
2 489541834 553583525
2 731279777 811513313
1 549864943 493384741
1 815378318 826084592
2 369622093 374205455
1 78240781 821999998
2 241667193 243982581

Sample Output 3

C - Even Sum Triplet

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

長さ N の整数列 A=(A_1, A_2, \dots, A_N), B=(B_1, B_2, \dots, B_N) が与えられます。

あなたは以下の操作を好きな回数行うことができます。

A_i+A_{i+1}+A_{i+2} が偶数であるような整数 i\ (1 \leq i \leq N-2) を選ぶ。そして A_i, A_{i+1}, A_{i+2} を好きに並び替える。

A を B に一致させることができるか判定してください。

制約

3 \leq N \leq 2 \times 10^5
1 \leq A_i, B_i \leq 2 \times 10^5
入力される値はすべて整数

入力

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

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

出力

A を B に一致させることが可能な場合は Yes を、そうでない場合は No を出力せよ。

入力例 1

5
1 2 3 4 5
3 1 2 4 5

出力例 1

Yes

A_1+A_2+A_3 は 1+2+3=6 であり偶数なので、操作では i=1 を選ぶことができます。

i=1 を選んで操作し、A_1, A_2, A_3 を A_3, A_1, A_2 に並び替えると、 A は (3, 1, 2, 4, 5) に変化します。

この操作により A を B に一致させることができるので、 Yes を出力します。

入力例 2

5
1 2 4 6 5
5 1 4 2 6

出力例 2

No

入力例 3

9
2 10 4 3 6 2 6 8 5
2 4 10 3 8 6 6 2 5

出力例 3

Yes

Score : 700 points

Problem Statement

You are given integer sequences of length N: A=(A_1, A_2, \dots, A_N) and B=(B_1, B_2, \dots, B_N).

You may perform the following operation any number of times:

Choose an integer i\ (1 \leq i \leq N-2) such that A_i+A_{i+1}+A_{i+2} is even. Then, rearrange A_i, A_{i+1}, A_{i+2} as you like.

Determine whether it is possible to make A equal B.

Constraints

3 \leq N \leq 2 \times 10^5
1 \leq A_i, B_i \leq 2 \times 10^5
All values in the input are integers.

Input

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

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

Output

If it is possible to make A equal B, print Yes; otherwise, print No.

Sample Input 1

5
1 2 3 4 5
3 1 2 4 5

Sample Output 1

Yes

A_1+A_2+A_3 is 1+2+3=6, which is even, so you can choose i=1.

If you choose i=1 and rearrange A_1, A_2, A_3 into A_3, A_1, A_2, then A becomes (3, 1, 2, 4, 5).

Now A equals B, so you should print Yes.

Sample Input 2

5
1 2 4 6 5
5 1 4 2 6

Sample Output 2

No

Sample Input 3

9
2 10 4 3 6 2 6 8 5
2 4 10 3 8 6 6 2 5

Sample Output 3

Yes

D - Avoid Coprime Game

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

2 つの非負整数 x, y に対し \gcd(x,y) を x と y の最大公約数とします（ただし、 x=0 のときは \gcd(x,y)=\gcd(y,x)=y とします）。

黒板に N 個の整数が書かれており、そのうち i 番目の整数は A_i です。これら N 個の整数の最大公約数は 1 です。

高橋君と青木君が 2 人で対戦ゲームをします。整数 G を G=0 で初期化した後、2 人は高橋君から始めて交互に以下の操作を繰り返します。

黒板に書かれている数のうち、\gcd(G,a)\neq 1 をみたす数 a を選んで消し、G を \gcd(G,a) で置き換える。

先に操作を行えなくなったほうが負けです。

各 i\ (1\leq i \leq N) について、高橋君が最初の手番で i 番目の整数を選んだ後、両者が最善を尽くした場合、どちらが勝つか判定してください。

制約

2 \leq N \leq 2 \times 10^5
2 \leq A_i \leq 2 \times 10^5
N 個の整数 A_i \ (1\leq i \leq N) の最大公約数は 1
与えられる入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N

出力

N 行出力せよ。i 行目には高橋君が最初の手番で i 番目の整数を選んだ後、両者が最善を尽くした場合、高橋君が勝つ場合は Takahashi を、青木君が勝つ場合は Aoki を出力せよ。

入力例 1

4
2 3 4 6

出力例 1

Takahashi
Aoki
Takahashi
Aoki

例えば高橋君が最初の手番で 4 番目の整数 A_4=6 を選んだ場合、青木君が 2 番目の整数 A_2=3 を選ぶと G=3 となります。この後高橋君が選べる整数は存在しないので、青木君の勝利となります。よって 4 行目には Aoki を出力します。

入力例 2

4
2 155 155 155

出力例 2

Takahashi
Takahashi
Takahashi
Takahashi

黒板には同じ整数が複数個書かれていることがあります。

入力例 3

20
2579 25823 32197 55685 73127 73393 74033 95252 104289 114619 139903 144912 147663 149390 155806 169494 175264 181477 189686 196663

出力例 3

Takahashi
Aoki
Takahashi
Aoki
Takahashi
Takahashi
Takahashi
Takahashi
Aoki
Takahashi
Takahashi
Aoki
Aoki
Aoki
Aoki
Aoki
Takahashi
Takahashi
Aoki
Takahashi

Score : 800 points

Problem Statement

For two non-negative integers x and y, let \gcd(x,y) be the greatest common divisor of x and y (for x=0, let \gcd(x,y)=\gcd(y,x)=y).

There are N integers on the blackboard, and the i-th integer is A_i. The greatest common divisor of these N integers is 1.

Takahashi and Aoki will play a game against each other. After initializing an integer G to 0, they will take turns performing the following operation, with Takahashi going first.

Choose a number a on the blackboard such that \gcd(G,a)\neq 1, erase it, and replace G with \gcd(G,a).

The first player unable to play loses.

For each i\ (1\leq i \leq N), determine the winner when Takahashi chooses the i-th integer on the blackboard in his first turn, and then both players play optimally.

Constraints

2 \leq N \leq 2 \times 10^5
2 \leq A_i \leq 2 \times 10^5
The greatest common divisor of the N integers A_i \ (1\leq i \leq N) is 1.
All values in the input are integers.

Input

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

N
A_1 A_2 \dots A_N

Output

Print N lines. The i-th line should contain the winner's name, Takahashi or Aoki, when Takahashi chooses the i-th integer on the blackboard in his first turn, and then both players play optimally.

Sample Input 1

4
2 3 4 6

Sample Output 1

Takahashi
Aoki
Takahashi
Aoki

For instance, when Takahashi chooses the fourth integer A_4=6 in his first turn, Aoki can then choose the second integer A_2=3 to make G=3. Now, Takahashi cannot choose anything, so Aoki wins. Thus, the fourth line should contain Aoki.

Sample Input 2

4
2 155 155 155

Sample Output 2

Takahashi
Takahashi
Takahashi
Takahashi

The blackboard may contain the same integer multiple times.

Sample Input 3

20
2579 25823 32197 55685 73127 73393 74033 95252 104289 114619 139903 144912 147663 149390 155806 169494 175264 181477 189686 196663

Sample Output 3

Takahashi
Aoki
Takahashi
Aoki
Takahashi
Takahashi
Takahashi
Takahashi
Aoki
Takahashi
Takahashi
Aoki
Aoki
Aoki
Aoki
Aoki
Takahashi
Takahashi
Aoki
Takahashi

E - Split and Square

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

非負整数からなる集合 X に対し、X に属する 2 つの整数（同じ整数でもよい）のビット単位 \mathrm{XOR} として表せるような非負整数からなる集合を f(X) と表します。例えば X=\lbrace 1, 2, 4\rbrace に対し f(X) は \lbrace 0, 3, 5, 6\rbrace となります。

N 個の 2^M 未満の非負整数からなる集合 S=\lbrace A_1, A_2, \dots, A_N\rbrace が与えられます。

あなたは以下の操作を好きな回数行えます。

S を 2 つの集合 T_1, T_2 に分ける（ T_1, T_2 のいずれかが空集合になってもよい）。その後、 S を f(T_1), f(T_2) の和集合で置き換える。

S を \lbrace 0\rbrace にするのに必要な最小の操作回数を求めてください。

ビット単位 \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)。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。

制約

1 \leq N \leq 300
1 \leq M \leq 300
0 \leq A_i < 2^{M}
A_i\ (1\leq i \leq N) は互いに相異なる
各 A_i は 2 進表記でちょうど M 桁で与えられる（ A_i が M 桁より少ない場合、 leading zero をつけて与えられる）
与えられる入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1
A_2
\vdots
A_N

出力

答えを出力せよ。

入力例 1

出力例 1

1 回目の操作では T_1=\lbrace 0, 1\rbrace, T_2=\lbrace 2, 3\rbrace と分けると f(T_1) =\lbrace 0, 1\rbrace, f(T_2) =\lbrace 0, 1\rbrace なので S は \lbrace 0, 1\rbrace に置き換わります。

2 回目の操作で T_1=\lbrace 0\rbrace, T_2=\lbrace 1\rbrace と分けると S=\lbrace 0\rbrace となります。

2 回未満の操作で S を \lbrace 0\rbrace にすることはできないので答えは 2 となります。

入力例 2

1 8
10011011

出力例 2

1 回目の操作で T_1=\lbrace 155\rbrace, T_2=\lbrace \rbrace と分けると S は \lbrace 0\rbrace になります。操作の際は T_1, T_2 のいずれかが空集合になっても構いません。

入力例 3

1 2
00

出力例 3

はじめから S=\lbrace 0\rbrace であり、操作する必要がありません。

入力例 4

20 20
10011011111101101111
10100111100001111100
10100111100110001111
10011011100011011111
11001000001110011010
10100111111011000101
11110100001001110010
10011011100010111001
11110100001000011010
01010011101011010011
11110100010000111100
01010011101101101111
10011011100010110111
01101111101110001110
00111100000101111010
01010011101111010100
10011011100010110100
01010011110010010011
10100111111111000001
10100111111000010101

出力例 4

Score : 900 points

Problem Statement

For a set X of non-negative integers, let f(X) denote the set of non-negative integers that can be represented as the bitwise \mathrm{XOR} of two integers (possibly the same) in X. As an example, for X=\lbrace 1, 2, 4\rbrace, we have f(X)=\lbrace 0, 3, 5, 6\rbrace.

You are given a set of N non-negative integers less than 2^M: S=\lbrace A_1, A_2, \dots, A_N\rbrace.

You may perform the following operation any number of times.

Divide S into two sets T_1 and T_2 (one of them may be empty). Then, replace S with the union of f(T_1) and f(T_2).

Find the minimum number of operations needed to make S=\lbrace 0\rbrace.

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 binary, the k-th lowest bit (k \geq 0) is 1 if exactly one of the k-th lowest bits of A and B is 1, and 0 otherwise.

For instance, 3 \oplus 5 = 6 (in binary: 011 \oplus 101 = 110).
Generally, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k), which can be proved to be independent of the order of p_1, p_2, p_3, \dots, p_k.

Constraints

1 \leq N \leq 300
1 \leq M \leq 300
0 \leq A_i < 2^{M}
A_i\ (1\leq i \leq N) are pairwise distinct.
Each A_i is given with exactly M digits in binary (possibly with leading zeros).
All values in the input are integers.

Input

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

N M
A_1
A_2
\vdots
A_N

Output

Print the answer.

Sample Input 1

Sample Output 1

In the first operation, you can divide S into T_1=\lbrace 0, 1\rbrace, T_2=\lbrace 2, 3\rbrace, for which f(T_1) =\lbrace 0, 1\rbrace, f(T_2) =\lbrace 0, 1\rbrace, replacing S with \lbrace 0, 1\rbrace.

In the second operation, you can divide S into T_1=\lbrace 0\rbrace, T_2=\lbrace 1\rbrace, making S=\lbrace 0\rbrace.

There is no way to make S=\lbrace 0\rbrace in fewer than two operations, so the answer is 2.

Sample Input 2

1 8
10011011

Sample Output 2

In the first operation, you can divide S into T_1=\lbrace 155\rbrace, T_2=\lbrace \rbrace, making S=\lbrace 0\rbrace. Note that T_1 or T_2 may be empty.

Sample Input 3

1 2
00

Sample Output 3

We have S=\lbrace 0\rbrace from the beginning; no operation is needed.

Sample Input 4

20 20
10011011111101101111
10100111100001111100
10100111100110001111
10011011100011011111
11001000001110011010
10100111111011000101
11110100001001110010
10011011100010111001
11110100001000011010
01010011101011010011
11110100010000111100
01010011101101101111
10011011100010110111
01101111101110001110
00111100000101111010
01010011101111010100
10011011100010110100
01010011110010010011
10100111111111000001
10100111111000010101

Sample Output 4

F - Directable as Desired

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

長さ N の非負整数列 D=(D_1, D_2, \dots, D_N) が与えられます。

1 から N までの番号が付いた N 頂点のラベル付き木のうち、以下の条件を満たすようなものの個数を 998244353 で割った余りを求めてください。

N-1 本の辺を適切に向き付けすることで、各頂点 i\ (1\leq i \leq N) の出次数をちょうど D_i にすることができる。

制約

2 \leq N \leq 2 \times 10^5
0 \leq D_i \leq N-1
\sum_{i=1}^{N} D_i = N-1
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
D_1 D_2 \dots D_N

出力

答えを出力してください。

入力例 1

4
0 1 0 2

出力例 1

条件を満たす木（およびその向き付けの例）は下の 5 種類です。

入力例 2

5
0 1 1 1 1

出力例 2

入力例 3

15
0 0 0 0 0 0 0 1 1 1 1 1 2 3 4

出力例 3

63282877

Score : 1000 points

Problem Statement

You are given a sequence of N non-negative integers: D=(D_1, D_2, \dots, D_N).

Find the number of labeled trees with N vertices numbered 1 to N that satisfy the following condition, modulo 998244353.

There is a way to direct the N-1 edges so that the outdegree of each vertex i\ (1\leq i \leq N) is D_i.

Constraints

2 \leq N \leq 2 \times 10^5
0 \leq D_i \leq N-1
\sum_{i=1}^{N} D_i = N-1
All values in the input are integers.

Input

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

N
D_1 D_2 \dots D_N

Output

Print the answer.

Sample Input 1

4
0 1 0 2

Sample Output 1

Below are the five trees that satisfy the condition, directed in a desired way.

Sample Input 2

5
0 1 1 1 1

Sample Output 2

Sample Input 3

15
0 0 0 0 0 0 0 1 1 1 1 1 2 3 4

Sample Output 3

63282877