AtCoder Daily Training MEDIUM 2025/04/09 18:00start

C - Cat

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

長さ N の文字列 S が与えられます。

S に連続して含まれる na を全て nya に置き換えて得られる文字列を答えてください。

制約

N は 1 以上 1000 以下の整数
S は英小文字からなる長さ N の文字列

入力

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

N
S

出力

答えを出力せよ。

入力例 1

4
naan

出力例 1

nyaan

naan に連続して含まれる na を全て nya に置き換えて得られる文字列は nyaan です。

入力例 2

4
near

出力例 2

near

S に na が連続して含まれないこともあります。

入力例 3

8
national

出力例 3

nyationyal

Score : 200 points

Problem Statement

You are given a string S of length N.

Find the string obtained by replacing all contiguous occurrences of na in S with nya.

Constraints

N is an integer between 1 and 1000, inclusive.
S is a string of length N consisting of lowercase English letters.

Input

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

N
S

Output

Print the answer.

Sample Input 1

4
naan

Sample Output 1

nyaan

Replacing all contiguous occurrences of na in naan with nya results in the string nyaan.

Sample Input 2

4
near

Sample Output 2

near

S may not contain a contiguous na.

Sample Input 3

8
national

Sample Output 3

nyationyal

D - Tetrahedral Number

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

整数 N が与えられます。

非負整数の組 (x,y,z) であって x+y+z\leq N を満たすものを辞書順で小さい方から順に全て出力してください。

非負整数の組の辞書順とは？

非負整数の組 (x,y,z) が (x',y',z') より辞書順で小さいとは、下記のいずれかが成り立つことを言います。

x < x' である
x=x' かつ y< y' である
x=x' かつ y=y' かつ z< z' である

制約

0 \leq N \leq 21
N は整数である

入力

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

出力

非負整数の組 (x,y,z) であって x+y+z\leq N を満たすものを、1 行に 1 組ずつ x,y,z を空白区切りで、辞書順で小さい方から順に全て出力せよ。

入力例 1

出力例 1

入力例 2

出力例 2

Score : 150 points

Problem Statement

You are given an integer N.

Print all triples of non-negative integers (x,y,z) such that x+y+z\leq N in ascending lexicographical order.

What is lexicographical order for non-negative integer triples?

A triple of non-negative integers (x,y,z) is said to be lexicographically smaller than (x',y',z') if and only if one of the following holds:

x < x';
x=x' and y< y';
x=x' and y=y' and z< z'.

Constraints

0 \leq N \leq 21
N is an integer.

Input

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

Output

Print all triples of non-negative integers (x,y,z) such that x+y+z\leq N in ascending lexicographical order, with x,y,z separated by spaces, one triple per line.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

E - Shortest Duplicate Subarray

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

正整数 N と、長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。

A の空でない連続部分列であって、同じ値を複数個含むようなものが存在するか判定してください。存在するならばそのようなもののうち最も短いものの長さを求めてください。

制約

1\leq N\leq 2\times 10^5
1\leq A_i\leq 10^6 (1\leq i\leq N)
入力はすべて整数

入力

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

N
A_1 A_2 \dots A_N

出力

問題文中の条件を満たす連続部分列が存在しないならば -1 と出力せよ。存在するならば、そのようなもののうち最も短いものの長さを出力せよ。

入力例 1

5
3 9 5 3 1

出力例 1

(3,9,5,3) と (3,9,5,3,1) が条件を満たします。短いのは (3,9,5,3) で、その長さは 4 です。

入力例 2

4
2 5 3 1

出力例 2

-1

条件を満たす連続部分列は存在しません。

入力例 3

10
1 1 2 3 5 8 13 21 34 55

出力例 3

Score : 300 points

Problem Statement

You are given a positive integer N and an integer sequence A = (A_1,A_2,\dots,A_N) of length N.

Determine whether there exists a non-empty (contiguous) subarray of A that has a repeated value, occurring multiple times in A. If such a subarray exists, find the length of the shortest such subarray.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq A_i \leq 10^6 \ (1 \leq i \leq N)
All input values are integers.

Input

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

N
A_1 A_2 \dots A_N

Output

If there is no (contiguous) subarray satisfying the condition in the problem statement, print -1. Otherwise, print the length of the shortest such subarray.

Sample Input 1

5
3 9 5 3 1

Sample Output 1

(3,9,5,3) and (3,9,5,3,1) satisfy the condition. The shorter one is (3,9,5,3), which has length 4.

Sample Input 2

4
2 5 3 1

Sample Output 2

-1

There is no subarray that satisfies the condition.

Sample Input 3

10
1 1 2 3 5 8 13 21 34 55

Sample Output 3

F - RANDOM

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

# と . からなる H 行 W 列の図形 S,T が与えられます。
図形 S は H 個の文字列として与えられ、 S_i の j 文字目は S の i 行 j 列にある要素を表します。 T についても同様です。

S の列を並べ替えて T と等しくできるか判定してください。

但し、図形 X の列を並べ替えるとは、以下の操作を言います。

(1,2,\dots,W) の順列 P=(P_1,P_2,\dots,P_W) をひとつ選択する。
その後、全ての 1 \le i \le H を満たす整数 i について、以下の操作を同時に行う。
- 1 \le j \le W を満たす全ての整数 j について同時に、 X の i 行 j 列にある要素を i 行 P_j 列にある要素に置き換える。

制約

H,W は整数
1 \le H,W
1 \le H \times W \le 4 \times 10^5
S_i,T_i は # と . からなる長さ W の文字列

入力

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

H W
S_1
S_2
\vdots
S_H
T_1
T_2
\vdots
T_H

出力

S を T と等しくできるなら Yes 、そうでないなら No と出力せよ。

入力例 1

3 4
##.#
##..
#...
.###
..##
...#

出力例 1

Yes

例えば S の 3,4,2,1 列目をこの順に左から並べ替えた場合、 S を T と等しくできます。

入力例 2

3 3
#.#
.#.
#.#
##.
##.
.#.

出力例 2

No

この入力では、 S を T と等しくすることができません。

入力例 3

2 1
#
.
#
.

出力例 3

Yes

S=T である場合もあります。

入力例 4

8 7
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
....###
####...
....###
####...
....###
####...
....###
####...

出力例 4

Yes

Score : 300 points

Problem Statement

You are given patterns S and T consisting of # and ., each with H rows and W columns.
The pattern S is given as H strings, and the j-th character of S_i represents the element at the i-th row and j-th column. The same goes for T.

Determine whether S can be made equal to T by rearranging the columns of S.

Here, rearranging the columns of a pattern X is done as follows.

Choose a permutation P=(P_1,P_2,\dots,P_W) of (1,2,\dots,W).
Then, for every integer i such that 1 \le i \le H, simultaneously do the following.
- For every integer j such that 1 \le j \le W, simultaneously replace the element at the i-th row and j-th column of X with the element at the i-th row and P_j-th column.

Constraints

H and W are integers.
1 \le H,W
1 \le H \times W \le 4 \times 10^5
S_i and T_i are strings of length W consisting of # and ..

Input

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

H W
S_1
S_2
\vdots
S_H
T_1
T_2
\vdots
T_H

Output

If S can be made equal to T, print Yes; otherwise, print No.

Sample Input 1

3 4
##.#
##..
#...
.###
..##
...#

Sample Output 1

Yes

If you, for instance, arrange the 3-rd, 4-th, 2-nd, and 1-st columns of S in this order from left to right, S will be equal to T.

Sample Input 2

3 3
#.#
.#.
#.#
##.
##.
.#.

Sample Output 2

No

In this input, S cannot be made equal to T.

Sample Input 3

2 1
#
.
#
.

Sample Output 3

Yes

It is possible that S=T.

Sample Input 4

8 7
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
....###
####...
....###
####...
....###
####...
....###
####...

Sample Output 4

Yes

G - Stone XOR

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

袋 1, 袋 2, \ldots, 袋 N と番号づけられた N 個の袋があります。
袋 i (1\leq i\leq N) には A_i 個の石が入っています。

高橋君は次の操作を好きなだけ（0 回でも良い）繰り返すことができます。

2 つの袋 A, B を選び、袋 A に入っている石を すべて 袋 B に入れる。

操作を繰り返した後の状態における次の値としてあり得るものが何個あるか求めてください。

袋 i に入っている石の個数を B_i として、B_1\oplus B_2\oplus\cdots\oplus B_N の値。
ただし、\oplus は排他的論理和を表す。

排他的論理和とは

非負整数 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 個の非負整数 x_1, x_2, \ldots, x_k の排他的論理和 x_1\oplus x_2\oplus\cdots\oplus x_k は (\cdots((x_1 \oplus x_2) \oplus x_3) \oplus \cdots \oplus x_k) と定義され、これは x_1, x_2, \ldots, x_k の順番によらないことが証明できます。

なお、問題の制約下において、操作を繰り返した後の状態における上記の値としてあり得るものが有限個しかないことが証明できます。

制約

2\leq N \leq 12
1\leq A_i \leq 10^{17}
入力はすべて整数

入力

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

N
A_1 A_2 \ldots A_N

出力

高橋君が操作を繰り返した後の状態における、問題文中で定義された値としてあり得るものの個数を出力せよ。

入力例 1

3
2 5 7

出力例 1

例えば、高橋君が袋 A, B として袋 1, 3 を選び、操作を行ったとすると、袋 1,2,3 に入っている石はそれぞれ 0,5,9 となります。
ここで高橋君が操作を終了したとき、この状態における、袋に入っている石の個数の排他的論理和は 0\oplus 5\oplus 9=12 となります。

他に、高橋君が操作を繰り返した後の状態における、袋に入っている石の個数の排他的論理和としてあり得るものは 0,14 があります。
よって、あり得る値は 0,12,14 の 3 個であるため、3 を出力します。

入力例 2

2
100000000000000000 100000000000000000

出力例 2

入力例 3

6
71 74 45 34 31 60

出力例 3

Score : 400 points

Problem Statement

There are N bags, labeled bag 1, bag 2, \ldots, bag N.
Bag i (1 \leq i \leq N) contains A_i stones.

Takahashi can perform the following operation any number of times, possibly zero:

Choose two bags A and B, and move all stones from bag A into bag B.

Find the number of different possible values for the following after repeating the operation.

B_1 \oplus B_2 \oplus \cdots \oplus B_N, where B_i is the final number of stones in bag i.
Here, \oplus denotes bitwise XOR.

About bitwise XOR

For non-negative integers a and b, the bitwise XOR a \oplus b is defined as follows:

In the binary representation of a \oplus b, the digit in the 2^k place (k \ge 0) is 1 if and only if exactly one of the digits in the 2^k place of a and b is 1; otherwise, it is 0.

For example, 3 \oplus 5 = 6 (in binary, 011 \oplus 101 = 110).
In general, for k non-negative integers x_1, x_2, \ldots, x_k, their bitwise XOR x_1 \oplus x_2 \oplus \cdots \oplus x_k is defined as (\cdots((x_1 \oplus x_2) \oplus x_3) \oplus \cdots) \oplus x_k, which does not depend on the order of x_1, x_2, \ldots, x_k.

It can be proved that under the constraints of this problem, the number of possible values is finite.

Constraints

2 \leq N \leq 12
1 \leq A_i \leq 10^{17}
All input values are integers.

Input

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

N
A_1 A_2 \ldots A_N

Output

Print the number of different possible values for B_1 \oplus B_2 \oplus \cdots \oplus B_N after repeating the operation.

Sample Input 1

3
2 5 7

Sample Output 1

For example, if Takahashi chooses bags 1 and 3 for the operation, then the numbers of stones in bags 1, 2, 3 become 0, 5, 9.
If he stops at this point, the XOR is 0 \oplus 5 \oplus 9 = 12.

The other possible XOR values after repeating the operation are 0 and 14.
Therefore, the possible values are 0, 12, 14; there are three values, so the output is 3.

Sample Input 2

2
100000000000000000 100000000000000000

Sample Output 2

Sample Input 3

6
71 74 45 34 31 60