AtCoder Beginner Contest 367

A - Shout Everyday

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

AtCoder 王国の住民は A 時になるとたこ焼きへの愛を叫ぶことになっています。

AtCoder 王国に住む高橋君は毎日 B 時に就寝し C 時に起床します。高橋君は、起きているときはたこ焼きへの愛を叫ぶことができ、寝ているときは叫ぶことができません。高橋君が毎日たこ焼きへの愛を叫ぶことができているか判定してください。ただし、一日は 24 時間であり、高橋君が寝ている時間は 24 時間未満であるとします。

制約

0\leq A,B,C\lt 24
A,B,C は相異なる
入力は全て整数

入力

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

A B C

出力

高橋君が毎日たこ焼きへの愛を叫ぶことができているならば Yes を、そうでないならば No を出力せよ。

入力例 1

21 8 14

出力例 1

Yes

高橋君は毎日 8 時に就寝し 14 時に起床します。21 時には起きているため、高橋君は毎日たこ焼きへの愛を叫ぶことができます。よって Yes を出力します。

入力例 2

0 21 7

出力例 2

No

高橋君は毎日 21 時に就寝し 7 時に起床します。0 時には起きていないため、高橋君は毎日たこ焼きへの愛を叫ぶことができません。よって No を出力します。

入力例 3

10 7 17

出力例 3

No

Score : 150 points

Problem Statement

In the Kingdom of AtCoder, residents are required to shout their love for takoyaki at A o'clock every day.

Takahashi, who lives in the Kingdom of AtCoder, goes to bed at B o'clock and wakes up at C o'clock every day (in the 24-hour clock). He can shout his love for takoyaki when he is awake, but cannot when he is asleep. Determine whether he can shout his love for takoyaki every day. Here, a day has 24 hours, and his sleeping time is less than 24 hours.

Constraints

0\leq A,B,C\lt 24
A, B, and C are pairwise different.
All input values are integers.

Input

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

A B C

Output

Print Yes if Takahashi can shout his love for takoyaki every day, and No otherwise.

Sample Input 1

21 8 14

Sample Output 1

Yes

Takahashi goes to bed at 8 o'clock and wakes up at 14 o'clock every day. He is awake at 21 o'clock, so he can shout his love for takoyaki every day. Therefore, print Yes.

Sample Input 2

0 21 7

Sample Output 2

No

Takahashi goes to bed at 21 o'clock and wakes up at 7 o'clock every day. He is not awake at 0 o'clock, so he cannot shout his love for takoyaki every day. Therefore, print No.

Sample Input 3

10 7 17

Sample Output 3

No

B - Cut .0

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

実数 X が小数点以下第 3 位まで与えられます。

実数 X を以下の条件を満たすように出力してください。

小数点以下の部分について、末尾に 0 を付けない
末尾に過剰な小数点を付けない

制約

0 \le X < 100
X は小数点以下第 3 位まで与えられる

入力

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

出力

答えを出力せよ。

入力例 1

1.012

出力例 1

1.012

1.012 はそのまま出力しても構いません。

入力例 2

12.340

出力例 2

12.34

12.340 を末尾に 0 を付けずに出力すると 12.34 となります。

入力例 3

99.900

出力例 3

99.9

99.900 を末尾に 0 を付けずに出力すると 99.9 となります。

入力例 4

0.000

出力例 4

0.000 を末尾に 0 や過剰な小数点を付けずに出力すると 0 となります。

Score : 150 points

Problem Statement

A real number X is given to the third decimal place.

Print the real number X under the following conditions.

The decimal part must not have trailing 0s.
There must not be an unnecessary trailing decimal point.

Constraints

0 \le X < 100
X is given to the third decimal place.

Input

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

Output

Output the answer.

Sample Input 1

1.012

Sample Output 1

1.012

1.012 can be printed as it is.

Sample Input 2

12.340

Sample Output 2

12.34

Printing 12.340 without the trailing 0 results in 12.34.

Sample Input 3

99.900

Sample Output 3

99.9

Printing 99.900 without the trailing 0s results in 99.9.

Sample Input 4

0.000

Sample Output 4

Printing 0.000 without trailing 0s or an unnecessary decimal point results in 0.

C - Enumerate Sequences

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

以下の条件を満たす長さ N の整数列を辞書順で小さい方から順に全て出力して下さい。

i 番目の要素は 1 以上 R_i 以下
総和が K の倍数

数列の辞書順とは？

数列 A = (A_1, \ldots, A_{|A|}) が B = (B_1, \ldots, B_{|B|}) より辞書順で真に小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。

|A|<|B| かつ (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}) である。
ある整数 1\leq i\leq \min\{|A|,|B|\} が存在して、下記の 2 つがともに成り立つ。
- (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
- A_i < B_i

制約

入力は全て整数
1 \le N \le 8
2 \le K \le 10
1 \le R_i \le 5

入力

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

N K
R_1 R_2 \dots R_N

出力

出力すべき数列が X 個あり、そのうち i 個目が A_i=(A_{i,1},A_{i,2},\dots,A_{i,N}) であったとき、答えを以下の形式で出力せよ。

A_{1,1} A_{1,2} \dots A_{1,N}
A_{2,1} A_{2,2} \dots A_{2,N}
\vdots
A_{X,1} A_{X,2} \dots A_{X,N}

入力例 1

3 2
2 1 3

出力例 1

1 1 2
2 1 1
2 1 3

出力すべき数列は 3 個で、辞書順で (1,1,2),(2,1,1),(2,1,3) です。

入力例 2

1 2
1

出力例 2

出力すべき数列が無い場合もあります。
この場合、出力は空で構いません。

入力例 3

5 5
2 3 2 3 2

出力例 3

Score : 300 points

Problem Statement

Print all integer sequences of length N that satisfy the following conditions, in ascending lexicographical order.

The i-th element is between 1 and R_i, inclusive.
The sum of all elements is a multiple of K.

What is lexicographical order for sequences?

A sequence A = (A_1, \ldots, A_{|A|}) is lexicographically smaller than B = (B_1, \ldots, B_{|B|}) if either 1. or 2. below holds:

|A|<|B| and (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}).
There exists an integer 1\leq i\leq \min\{|A|,|B|\} such that both of the following are true:
- (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
- A_i < B_i

Constraints

All input values are integers.
1 \le N \le 8
2 \le K \le 10
1 \le R_i \le 5

Input

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

N K
R_1 R_2 \dots R_N

Output

Print the answer in the following format, where X is the number of sequences to print, the i-th of which is A_i=(A_{i,1},A_{i,2},\dots,A_{i,N}):

A_{1,1} A_{1,2} \dots A_{1,N}
A_{2,1} A_{2,2} \dots A_{2,N}
\vdots
A_{X,1} A_{X,2} \dots A_{X,N}

Sample Input 1

3 2
2 1 3

Sample Output 1

1 1 2
2 1 1
2 1 3

There are three sequences to be printed, which are (1,1,2),(2,1,1),(2,1,3) in lexicographical order.

Sample Input 2

1 2
1

Sample Output 2

There may be no sequences to print.
In this case, the output can be empty.

Sample Input 3

5 5
2 3 2 3 2

Sample Output 3

D - Pedometer

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

湖の周りに N 個の休憩所があります。
休憩所には時計回りに 1,2,\dots,N の番号が付いています。
休憩所 i から休憩所 i+1 まで時計回りに歩くには A_i 歩かかります ( 但し、休憩所 N+1 は休憩所 1 を指します ) 。
休憩所 s から休憩所 t ( s \neq t ) まで時計回りに歩くのにかかる最小の歩数は M の倍数でした。
(s,t) の組として考えられるものの数を求めてください。

制約

入力は全て整数
2 \le N \le 2 \times 10^5
1 \le A_i \le 10^9
1 \le M \le 10^6

入力

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

N M
A_1 A_2 \dots A_N

出力

答えを整数として出力せよ。

入力例 1

4 3
2 1 4 3

出力例 1

休憩所 1 から休憩所 2 まで時計回りに歩くのにかかる最小の歩数は 2 歩で、これは 3 の倍数ではありません。
休憩所 1 から休憩所 3 まで時計回りに歩くのにかかる最小の歩数は 3 歩で、これは 3 の倍数です。
休憩所 1 から休憩所 4 まで時計回りに歩くのにかかる最小の歩数は 7 歩で、これは 3 の倍数ではありません。
休憩所 2 から休憩所 3 まで時計回りに歩くのにかかる最小の歩数は 1 歩で、これは 3 の倍数ではありません。
休憩所 2 から休憩所 4 まで時計回りに歩くのにかかる最小の歩数は 5 歩で、これは 3 の倍数ではありません。
休憩所 2 から休憩所 1 まで時計回りに歩くのにかかる最小の歩数は 8 歩で、これは 3 の倍数ではありません。
休憩所 3 から休憩所 4 まで時計回りに歩くのにかかる最小の歩数は 4 歩で、これは 3 の倍数ではありません。
休憩所 3 から休憩所 1 まで時計回りに歩くのにかかる最小の歩数は 7 歩で、これは 3 の倍数ではありません。
休憩所 3 から休憩所 2 まで時計回りに歩くのにかかる最小の歩数は 9 歩で、これは 3 の倍数です。
休憩所 4 から休憩所 1 まで時計回りに歩くのにかかる最小の歩数は 3 歩で、これは 3 の倍数です。
休憩所 4 から休憩所 2 まで時計回りに歩くのにかかる最小の歩数は 5 歩で、これは 3 の倍数ではありません。
休憩所 4 から休憩所 3 まで時計回りに歩くのにかかる最小の歩数は 6 歩で、これは 3 の倍数です。

以上より、求めるべき (s,t) の組の数は 4 個です。

入力例 2

2 1000000
1 1

出力例 2

入力例 3

9 5
9 9 8 2 4 4 3 5 3

出力例 3

Score : 400 points

Problem Statement

There are N rest areas around a lake.
The rest areas are numbered 1, 2, ..., N in clockwise order.
It takes A_i steps to walk clockwise from rest area i to rest area i+1 (where rest area N+1 refers to rest area 1).
The minimum number of steps required to walk clockwise from rest area s to rest area t (s \neq t) is a multiple of M.
Find the number of possible pairs (s,t).

Constraints

All input values are integers
2 \le N \le 2 \times 10^5
1 \le A_i \le 10^9
1 \le M \le 10^6

Input

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

N M
A_1 A_2 \dots A_N

Output

Print the answer as an integer.

Sample Input 1

4 3
2 1 4 3

Sample Output 1

The minimum number of steps to walk clockwise from rest area 1 to rest area 2 is 2, which is not a multiple of 3.
The minimum number of steps to walk clockwise from rest area 1 to rest area 3 is 3, which is a multiple of 3.
The minimum number of steps to walk clockwise from rest area 1 to rest area 4 is 7, which is not a multiple of 3.
The minimum number of steps to walk clockwise from rest area 2 to rest area 3 is 1, which is not a multiple of 3.
The minimum number of steps to walk clockwise from rest area 2 to rest area 4 is 5, which is not a multiple of 3.
The minimum number of steps to walk clockwise from rest area 2 to rest area 1 is 8, which is not a multiple of 3.
The minimum number of steps to walk clockwise from rest area 3 to rest area 4 is 4, which is not a multiple of 3.
The minimum number of steps to walk clockwise from rest area 3 to rest area 1 is 7, which is not a multiple of 3.
The minimum number of steps to walk clockwise from rest area 3 to rest area 2 is 9, which is a multiple of 3.
The minimum number of steps to walk clockwise from rest area 4 to rest area 1 is 3, which is a multiple of 3.
The minimum number of steps to walk clockwise from rest area 4 to rest area 2 is 5, which is not a multiple of 3.
The minimum number of steps to walk clockwise from rest area 4 to rest area 3 is 6, which is a multiple of 3.

Therefore, there are four possible pairs (s,t).

Sample Input 2

2 1000000
1 1

Sample Output 2

Sample Input 3

9 5
9 9 8 2 4 4 3 5 3

Sample Output 3

E - Permute K times

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

各要素が 1 以上 N 以下である長さ N の数列 X と、長さ N の数列 A が与えられます。
A に以下の操作を K 回行った結果を出力してください。

B_i=A_{X_i} なる B を新たな A とする

制約

入力は全て整数
1 \le N \le 2 \times 10^5
0 \le K \le 10^{18}
1 \le X_i \le N
1 \le A_i \le 2 \times 10^5

入力

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

N K
X_1 X_2 \dots X_N
A_1 A_2 \dots A_N

出力

操作後の A を A' としたとき、以下の形式で出力せよ。

A'_1 A'_2 \dots A'_N

入力例 1

7 3
5 2 6 3 1 4 6
1 2 3 5 7 9 11

出力例 1

7 2 3 5 1 9 3

この入力では X=(5,2,6,3,1,4,6) で、操作前の数列 A=(1,2,3,5,7,9,11) です。

操作を 1 度行うと、数列は (7,2,9,3,1,5,9) となります。
操作を 2 度行うと、数列は (1,2,5,9,7,3,5) となります。
操作を 3 度行うと、数列は (7,2,3,5,1,9,3) となります。

入力例 2

4 0
3 4 1 2
4 3 2 1

出力例 2

4 3 2 1

操作が一度も行われない場合もあります。

入力例 3

9 1000000000000000000
3 7 8 5 9 3 7 4 2
9 9 8 2 4 4 3 5 3

出力例 3

3 3 3 3 3 3 3 3 3

Score : 450 points

Problem Statement

You are given a sequence X of length N where each element is between 1 and N, inclusive, and a sequence A of length N.
Print the result of performing the following operation K times on A.

Replace A with B such that B_i = A_{X_i}.

Constraints

All input values are integers.
1 \le N \le 2 \times 10^5
0 \le K \le 10^{18}
1 \le X_i \le N
1 \le A_i \le 2 \times 10^5

Input

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

N K
X_1 X_2 \dots X_N
A_1 A_2 \dots A_N

Output

Let A' be the sequence A after the operations. Print it in the following format:

A'_1 A'_2 \dots A'_N

Sample Input 1

7 3
5 2 6 3 1 4 6
1 2 3 5 7 9 11

Sample Output 1

7 2 3 5 1 9 3

In this input, X=(5,2,6,3,1,4,6) and the initial sequence is A=(1,2,3,5,7,9,11).

After one operation, the sequence is (7,2,9,3,1,5,9).
After two operations, the sequence is (1,2,5,9,7,3,5).
After three operations, the sequence is (7,2,3,5,1,9,3).

Sample Input 2

4 0
3 4 1 2
4 3 2 1

Sample Output 2

4 3 2 1

There may be cases where no operations are performed.

Sample Input 3

9 1000000000000000000
3 7 8 5 9 3 7 4 2
9 9 8 2 4 4 3 5 3

Sample Output 3

3 3 3 3 3 3 3 3 3

F - Rearrange Query

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

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

Q 個のクエリが与えられるので順に処理してください。i 番目のクエリは以下で説明されます。

正整数 l_i,r_i,L_i,R_i が与えられる。数列 (A_{l_i},A_{l_i+1},\ldots,A_{r_i}) を並び替えることで (B_{L_i},B_{L_i+1},\ldots,B_{R_i}) に一致させることができるならば Yes を、できないならば No を出力せよ。

制約

1\leq N,Q\leq 2\times 10^5
1\leq A_i,B_i\leq N
1\leq l_i \leq r_i\leq N
1\leq L_i \leq R_i\leq N
入力は全て整数

入力

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

N Q
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
l_1 r_1 L_1 R_1
l_2 r_2 L_2 R_2
\vdots
l_Q r_Q L_Q R_Q

出力

Q 行出力せよ。i 行目には i 番目のクエリの答えを出力せよ。

入力例 1

出力例 1

Yes
No
No
Yes

1 番目のクエリについて、(1,2,3) を並び替えることで (2,3,1) に一致させることができます。よって Yes を出力します。
2 番目のクエリについて、(1,2) をどのように並び替えても (1,4,2) に一致させることができません。よって No を出力します。
3 番目のクエリについて、(1,2,3,2) をどのように並び替えても (3,1,4,2) に一致させることができません。よって No を出力します。
4 番目のクエリについて、(1,2,3,2,4) を並び替えることで (2,3,1,4,2) に一致させることができます。よって Yes を出力します。

入力例 2

出力例 2

Yes
Yes
No
No

Score : 500 points

Problem Statement

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

You are given Q queries to process in order. The i-th query is explained below.

You are given positive integers l_i,r_i,L_i,R_i. Print Yes if it is possible to rearrange the subsequence (A_{l_i},A_{l_i+1},\ldots,A_{r_i}) to match the subsequence (B_{L_i},B_{L_i+1},\ldots,B_{R_i}), and No otherwise.

Constraints

1\leq N,Q\leq 2\times 10^5
1\leq A_i,B_i\leq N
1\leq l_i \leq r_i\leq N
1\leq L_i \leq R_i\leq N
All input values are integers.

Input

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

N Q
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
l_1 r_1 L_1 R_1
l_2 r_2 L_2 R_2
\vdots
l_Q r_Q L_Q R_Q

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

Sample Output 1

Yes
No
No
Yes

For the 1st query, it is possible to rearrange (1,2,3) to match (2,3,1). Hence, we print Yes.
For the 2nd query, it is impossible to rearrange (1,2) in any way to match (1,4,2). Hence, we print No.
For the 3rd query, it is impossible to rearrange (1,2,3,2) in any way to match (3,1,4,2). Hence, we print No.
For the 4th query, it is possible to rearrange (1,2,3,2,4) to match (2,3,1,4,2). Hence, we print Yes.

Sample Input 2

Sample Output 2

Yes
Yes
No
No

G - Sum of (XOR^K or 0)

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 675 点

問題文

正整数 N,M,K および非負整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

非空な非負整数列 B=(B_1,B_2,\ldots,B_{|B|}) に対して、スコアを以下で定めます。

B の長さが M の倍数のとき (B_1 \oplus B_2 \oplus \dots \oplus B_{|B|})^K
そうでないとき 0

ただし、\oplus はビットごとの排他的論理和を表します。

A の非空な部分列 2^N-1 個それぞれに対するスコアの総和を 998244353 で割った余りを求めてください。

ビットごとの排他的論理和とは

非負整数 A, B のビットごとの排他的論理和 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, \dots, p_k の排他的論理和は (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k) と定義され、これは p_1, \dots, p_k の順番によらないことが証明できます。

制約

1\leq N,K\leq 2\times 10^5
1\leq M\leq 100
0\leq A_i\lt 2^{20}
入力は全て整数

入力

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

N M K
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

3 2 2
1 2 3

出力例 1

A の非空な部分列 2^3-1=7 個それぞれのスコアは以下のようになります。

(1)：0
(2)：0
(3)：0
(1,2)：(1\oplus2)^2=9
(1,3)：(1\oplus3)^2=4
(2,3)：(2\oplus3)^2=1
(1,2,3)：0

よって求める総和は 0+0+0+9+4+1+0=14 です。

入力例 2

10 5 3
100 100 100 100 100 100 100 100 100 100

出力例 2

252000000

入力例 3

16 4 100
7053 3876 3178 8422 7802 5998 2334 6757 6889 6637 7365 9495 7848 9026 7312 6558

出力例 3

432440016

Score : 675 points

Problem Statement

You are given positive integers N, M, K, and a sequence of non-negative integers: A=(A_1,A_2,\ldots,A_N).

For a non-empty non-negative integer sequence B=(B_1,B_2,\ldots,B_{|B|}), we define its score as follows.

If the length of B is a multiple of M: (B_1 \oplus B_2 \oplus \dots \oplus B_{|B|})^K
Otherwise: 0

Here, \oplus represents the bitwise XOR.

Find the sum, modulo 998244353, of the scores of the 2^N-1 non-empty subsequences of A.

What is bitwise XOR?

The bitwise XOR of non-negative integers A and B, denoted as A \oplus B, is defined as follows:

In the binary representation of A \oplus B, the digit at position 2^k (k \geq 0) is 1 if exactly one of A and B has a 1 in that position in their binary representations, and 0 otherwise.

For example, 3 \oplus 5 = 6 (in binary: 011 \oplus 101 = 110).
In general, the XOR of k integers p_1, \dots, p_k is defined as (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k), and it can be proved that this is independent of the order of p_1, \dots, p_k.

Constraints

1 \leq N,K \leq 2 \times 10^5
1 \leq M \leq 100
0 \leq A_i < 2^{20}
All input values are integers.

Input

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

N M K
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

3 2 2
1 2 3

Sample Output 1

Here are the scores of the 2^3-1=7 non-empty subsequences of A.

(1): 0
(2): 0
(3): 0
(1,2): (1\oplus2)^2=9
(1,3): (1\oplus3)^2=4
(2,3): (2\oplus3)^2=1
(1,2,3): 0

Therefore, the sought sum is 0+0+0+9+4+1+0=14.

Sample Input 2

10 5 3
100 100 100 100 100 100 100 100 100 100

Sample Output 2

252000000

Sample Input 3

16 4 100
7053 3876 3178 8422 7802 5998 2334 6757 6889 6637 7365 9495 7848 9026 7312 6558

Sample Output 3

432440016