AtCoder Daily Training HARD 2024/10/24 18:30start

E - Word Ladder

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

英小文字からなる文字列 S, T が与えられます。ここで、S と T の長さは等しいです。

X を空の配列とし、以下の操作を S と T が等しくなるまで繰り返します。

S の文字を 1 文字書き換え、X の末尾に S を追加する。

こうして得られる文字列の配列 X のうち要素数最小のものを求めてください。要素数最小のものが複数考えられる場合は、そのうち辞書順最小のものを求めてください。

文字列の配列の辞書順とは

長さ N の文字列 S = S_1 S_2 \ldots S_N が長さ N の文字列 T = T_1 T_2 \ldots T_N より辞書順で小さいとは、ある整数 1 \leq i \leq N が存在して下記の 2 つがともに成り立つことをいいます。

S_1 S_2 \ldots S_{i-1} = T_1 T_2 \ldots T_{i-1}
S_i が T_i よりアルファベット順で早い。

要素数 M の文字列の配列 X = (X_1,X_2,\ldots,X_M) が要素数 M の文字列の配列 Y = (Y_1,Y_2,\ldots,Y_M) より辞書順で小さいとは、ある整数 1 \leq j \leq M が存在して下記の 2 つがともに成り立つことをいいます。

(X_1,X_2,\ldots,X_{j-1}) = (Y_1,Y_2,\ldots,Y_{j-1})
X_j が Y_j より辞書順で小さい。

制約

S, T は英小文字からなる長さ 1 以上 100 以下の文字列
S と T の長さは等しい

入力

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

S
T

出力

答えの要素数を M として M + 1 行出力せよ。

1 行目には M の値を出力せよ。

i + 1 (1 \leq i \leq M) 行目には答えの i 番目の要素を出力せよ。

入力例 1

adbe
bcbc

出力例 1

3
acbe
acbc
bcbc

はじめ、S = adbe です。

以下のように操作することで、X = ( acbe , acbc , bcbc ) とすることができます。

S を acbe に書き換え、X の末尾に acbe を追加する。
S を acbc に書き換え、X の末尾に acbc を追加する。
S を bcbc に書き換え、X の末尾に bcbc を追加する。

入力例 2

abcde
abcde

出力例 2

入力例 3

afwgebrw
oarbrenq

出力例 3

8
aawgebrw
aargebrw
aarbebrw
aarbebnw
aarbebnq
aarbeenq
aarbrenq
oarbrenq

Score : 300 points

Problem Statement

You are given two strings S and T consisting of lowercase English letters. Here, S and T have equal lengths.

Let X be an empty array, and repeat the following operation until S equals T:

Change one character in S, and append S to the end of X.

Find the array of strings X with the minimum number of elements obtained in this way. If there are multiple such arrays with the minimum number of elements, find the lexicographically smallest one among them.

What is lexicographical order on arrays of strings?

A string S = S_1 S_2 \ldots S_N of length N is lexicographically smaller than a string T = T_1 T_2 \ldots T_N of length N if there exists an integer 1 \leq i \leq N such that both of the following are satisfied:

S_1 S_2 \ldots S_{i-1} = T_1 T_2 \ldots T_{i-1}
S_i comes earlier than T_i in alphabetical order.

An array of strings X = (X_1,X_2,\ldots,X_M) with M elements is lexicographically smaller than an array of strings Y = (Y_1,Y_2,\ldots,Y_M) with M elements if there exists an integer 1 \leq j \leq M such that both of the following are satisfied:

(X_1,X_2,\ldots,X_{j-1}) = (Y_1,Y_2,\ldots,Y_{j-1})
X_j is lexicographically smaller than Y_j.

Constraints

S and T are strings consisting of lowercase English letters with length between 1 and 100, inclusive.
The lengths of S and T are equal.

Input

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

S
T

Output

Let M be the number of elements in the desired array. Print M + 1 lines.

The first line should contain the value of M.

The i + 1-th line (1 \leq i \leq M) should contain the i-th element of the array.

Sample Input 1

adbe
bcbc

Sample Output 1

3
acbe
acbc
bcbc

Initially, S = adbe.

We can obtain X = ( acbe , acbc , bcbc ) by performing the following operations:

Change S to acbe and append acbe to the end of X.
Change S to acbc and append acbc to the end of X.
Change S to bcbc and append bcbc to the end of X.

Sample Input 2

abcde
abcde

Sample Output 2

Sample Input 3

afwgebrw
oarbrenq

Sample Output 3

8
aawgebrw
aargebrw
aarbebrw
aarbebnw
aarbebnq
aarbeenq
aarbrenq
oarbrenq

F - Σ

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

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

1 以上 K 以下の整数のうち、A の中に一度も現れないものの総和を求めてください。

制約

1\leq N \leq 2\times 10^5
1\leq K \leq 2\times 10^9
1\leq A_i \leq 2\times 10^9
入力は全て整数

入力

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

N K
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

4 5
1 6 3 1

出力例 1

1 以上 5 以下の整数のうち、A の中に一度も現れないものは 2,4,5 の 3 つです。

よって、それらの総和である 2+4+5=11 を出力します。

入力例 2

1 3
346

出力例 2

入力例 3

10 158260522
877914575 24979445 623690081 262703497 24979445 1822804784 1430302156 1161735902 923078537 1189330739

出力例 3

12523196466007058

Score: 250 points

Problem Statement

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

Find the sum of the integers between 1 and K, inclusive, that do not appear in the sequence A.

Constraints

1\leq N \leq 2\times 10^5
1\leq K \leq 2\times 10^9
1\leq A_i \leq 2\times 10^9
All input values are integers.

Input

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

N K
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

4 5
1 6 3 1

Sample Output 1

Among the integers between 1 and 5, three numbers, 2, 4, and 5, do not appear in A.

Thus, print their sum: 2+4+5=11.

Sample Input 2

1 3
346

Sample Output 2

Sample Input 3

10 158260522
877914575 24979445 623690081 262703497 24979445 1822804784 1430302156 1161735902 923078537 1189330739

Sample Output 3

12523196466007058

G - Bank

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

銀行に人 1, 人 2, \dots, 人 N が並んでいます。
Q 個のイベントが発生します。イベントは次の 3 種類のいずれかです。

1 : 受付に呼ばれていない人のうち、最も小さい番号の人が受付に呼ばれる。
2 x : 人 x が初めて受付に行く。(ここで、人 x はすでに 1 回以上受付に呼ばれている。)
3 : すでに受付に呼ばれているが受付に行っていない人のうち、最も小さい番号の人が再度呼ばれる。

3 種類目のイベントで受付に呼ばれる人の番号を呼ばれた順に出力してください。

制約

1 \leq N \leq 5 \times 10^5
2 \leq Q \leq 5 \times 10^5
全ての人が 1 回以上呼ばれているときに 1 種類目のイベントが発生することはない
2 種類目のイベントについて、人 x はすでに 1 回以上受付に呼ばれている
2 種類目のイベントについて、人 x が 2 回以上受付に行くことはない
呼ばれている人が全員すでに受付に行っているときに 3 種類目のイベントが発生することはない
3 種類目のイベントは少なくとも 1 回発生する
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。ここで \text{event}_i は i 番目のイベントを意味する。

N Q
\text{event}_1
\text{event}_2
\vdots
\text{event}_Q

イベントは次の 3 つのいずれかの形式で入力される。

2 x

出力

入力で与えられる 3 種類目のイベントの個数を X として、X 行出力せよ。
i 行目には、3 種類目のイベントのうち i 番目のもので呼ばれた人の番号を出力せよ。

入力例 1

出力例 1

1
2
4

i = 1, 2, \dots, Q について、i 番目のイベントが起こる前の時点での、受付に呼ばれたが受付に行っていない人の集合を列挙すると次のようになります。

i=1 : \lbrace \rbrace
i=2 : \lbrace 1\rbrace
i=3 : \lbrace 1,2\rbrace
i=4 : \lbrace 1,2\rbrace
i=5 : \lbrace 2\rbrace
i=6 : \lbrace 2,3\rbrace
i=7 : \lbrace 2\rbrace
i=8 : \lbrace 2\rbrace
i=9 : \lbrace 2,4\rbrace
i=10 : \lbrace 4\rbrace

3 種類目のイベントは i=3,7,10 のときに発生しているので、その時点での集合のうち番号が最小の人である 1, 2, 4 を出力します。

Score : 400 points

Problem Statement

N people, with ID numbers 1, 2, \dots, N, are lining up in front of a bank.
There will be Q events. The following three kinds of events can happen.

1 : The teller calls the person with the smallest ID number who has not been called.
2 x : The person with the ID number x comes to the teller for the first time. (Here, person x has already been called by the teller at least once.)
3 : The teller again calls the person with the smallest ID number who has already been called but has not come.

Print the ID numbers of the people called by the teller in events of the third kind.

Constraints

1 \leq N \leq 5 \times 10^5
2 \leq Q \leq 5 \times 10^5
There will not be an event of the first kind when all people have already been called at least once.
For each event of the second kind, the person with the ID number x has already been called by the teller at least once.
For each event of the second kind, the person with the ID number x will not come to the teller more than once.
There will not be an event of the third kind when all people who have already been called have come to the teller.
There is at least one event of the third kind.
All values in the input are integers.

Input

The input is given from Standard Input in the following format, where \text{event}_i denotes the i-th event:

N Q
\text{event}_1
\text{event}_2
\vdots
\text{event}_Q

The description of each event is in one of the following formats:

2 x

Output

Print X lines, where X is the number of events of the third kind.
The i-th line should contain the ID number of the person called in the i-th event of the third kind.

Sample Input 1

Sample Output 1

1
2
4

For each i = 1, 2, \dots, Q, shown below is the set of people who have already been called but have not come just before the i-th event.

i=1 : \lbrace \rbrace
i=2 : \lbrace 1\rbrace
i=3 : \lbrace 1,2\rbrace
i=4 : \lbrace 1,2\rbrace
i=5 : \lbrace 2\rbrace
i=6 : \lbrace 2,3\rbrace
i=7 : \lbrace 2\rbrace
i=8 : \lbrace 2\rbrace
i=9 : \lbrace 2,4\rbrace
i=10 : \lbrace 4\rbrace

The events for i=3,7,10 are of the third kind, so you should print the persons with the smallest ID numbers in the sets for those events: 1, 2, 4.

H - Erasing Vertices 2

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

N 頂点 M 辺の単純無向グラフ（すなわち、自己辺も多重辺もない無向グラフ）が与えられます。i 本目の辺は頂点 U_i と頂点 V_i を結んでいます。頂点 i には正整数 A_i が書かれています。

あなたは、以下の操作を N 回繰り返します。

まだ削除されていない頂点 x を選び、「頂点 x 」と「頂点 x を端点に持つ辺全て」を削除する。この操作のコストは、頂点 x と辺で直接結ばれていて、かつまだ削除されていない頂点に書かれている整数の総和である。

N 回の操作全体のコストを、1 回ごとの操作におけるコストのうちの最大値として定めます。操作全体のコストとして取り得る値の最小値を求めてください。

制約

1 \le N \le 2 \times 10^5
0 \le M \le 2 \times 10^5
1 \le A_i \le 10^9
1 \le U_i,V_i \le N
与えられるグラフは単純。
入力は全て整数。

入力

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

N M
A_1 A_2 \dots A_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M

出力

答えを出力せよ。

入力例 1

出力例 1

以下のように操作を行うことにより、N 回の操作のコストのうちの最大値を 3 にすることができます。

頂点 3 を選ぶ。コストは A_1=3 である。
頂点 1 を選ぶ。コストは A_2+A_4=3 である。
頂点 2 を選ぶ。コストは 0 である。
頂点 4 を選ぶ。コストは 0 である。

N 回の操作のコストのうちの最大値を 2 以下にすることはできないため、解は 3 です。

入力例 2

7 13
464 661 847 514 74 200 188
5 1
7 1
5 7
4 1
4 5
2 4
5 2
1 3
1 6
3 5
1 2
4 6
2 7

出力例 2

Score : 500 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The i-th edge connects Vertices U_i and V_i. Vertex i has a positive integer A_i written on it.

You will repeat the following operation N times.

Choose a Vertex x that is not removed yet, and remove Vertex x and all edges incident to Vertex x. The cost of this operation is the sum of the integers written on the vertices directly connected by an edge with Vertex x that are not removed yet.

We define the cost of the entire N operations as the maximum of the costs of the individual operations. Find the minimum possible cost of the entire operations.

Constraints

1 \le N \le 2 \times 10^5
0 \le M \le 2 \times 10^5
1 \le A_i \le 10^9
1 \le U_i,V_i \le N
The given graph is simple.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 \dots A_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M

Output

Print the answer.

Sample Input 1

Sample Output 1

By performing the operations as follows, the maximum of the costs of the N operations can be 3.

Choose Vertex 3. The cost is A_1=3.
Choose Vertex 1. The cost is A_2+A_4=3.
Choose Vertex 2. The cost is 0.
Choose Vertex 4. The cost is 0.

The maximum of the costs of the N operations cannot be 2 or less, so the solution is 3.

Sample Input 2

7 13
464 661 847 514 74 200 188
5 1
7 1
5 7
4 1
4 5
2 4
5 2
1 3
1 6
3 5
1 2
4 6
2 7

Sample Output 2

I - XOR on Grid Path

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

N 行 N 列のマス目があり、上から i \, (1 \leq i \leq N) 行目、左から j \, (1 \leq j \leq N) 列目のマスを (i, j) と表します。
マス (i, j) には非負整数 a_{i, j} が書かれています。

マス (i, j) にいるとき、マス (i+1, j), (i, j+1) のいずれかに移動することができます。ただし、マス目の外に出るような移動はできません。

マス (1, 1) から移動を繰り返してマス (N, N) にたどり着く方法であって、通ったマス（マス (1, 1), (N, N) を含む）に書かれた整数の排他的論理和が 0 となるようなものの総数を求めてください。

排他的論理和とは

整数 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 の順番によらないことが証明できます。

制約

2 \leq N \leq 20
0 \leq a_{i, j} \lt 2^{30} \, (1 \leq i, j \leq N)
入力は全て整数

入力

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

N
a_{1, 1} \ldots a_{1, N}
\vdots
a_{N, 1} \ldots a_{N, N}

出力

答えを出力せよ。

入力例 1

出力例 1

次の二通りの方法が条件を満たします。

(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3)
(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)

入力例 2

2
1 2
2 1

出力例 2

入力例 3

10
1 0 1 0 0 1 0 0 0 1
0 0 0 1 0 1 0 1 1 0
1 0 0 0 1 0 1 0 0 0
0 1 0 0 0 1 1 0 0 1
0 0 1 1 0 1 1 0 1 0
1 0 0 0 1 0 0 1 1 0
1 1 1 0 0 0 1 1 0 0
0 1 1 0 0 1 1 0 1 0
1 0 1 1 0 0 0 0 0 0
1 0 1 1 0 0 1 1 1 0

出力例 3

Score : 500 points

Problem Statement

There is a grid with N rows and N columns. We denote by (i, j) the square at the i-th (1 \leq i \leq N) row from the top and j-th (1 \leq j \leq N) column from the left.
Square (i, j) has a non-negative integer a_{i, j} written on it.

When you are at square (i, j), you can move to either square (i+1, j) or (i, j+1). Here, you are not allowed to go outside the grid.

Find the number of ways to travel from square (1, 1) to square (N, N) such that the exclusive logical sum of the integers written on the squares visited (including (1, 1) and (N, N)) is 0.

What is the exclusive logical sum?

The exclusive logical sum a \oplus b of two integers a and b is defined as follows.

The 2^k's place (k \geq 0) in the binary notation of a \oplus b is 1 if exactly one of the 2^k's places in the binary notation of a and b is 1; otherwise, it is 0.

For example, 3 \oplus 5 = 6 (In binary notation: 011 \oplus 101 = 110).
In general, the exclusive logical sum 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). We can prove that it is independent of the order of p_1, \dots, p_k.

Constraints

2 \leq N \leq 20
0 \leq a_{i, j} \lt 2^{30} \, (1 \leq i, j \leq N)
All values in the input are integers.

Input

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

N
a_{1, 1} \ldots a_{1, N}
\vdots
a_{N, 1} \ldots a_{N, N}

Output

Print the answer.

Sample Input 1

Sample Output 1

The following two ways satisfy the condition:

(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3);
(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3).

Sample Input 2

2
1 2
2 1

Sample Output 2

Sample Input 3

10
1 0 1 0 0 1 0 0 0 1
0 0 0 1 0 1 0 1 1 0
1 0 0 0 1 0 1 0 0 0
0 1 0 0 0 1 1 0 0 1
0 0 1 1 0 1 1 0 1 0
1 0 0 0 1 0 0 1 1 0
1 1 1 0 0 0 1 1 0 0
0 1 1 0 0 1 1 0 1 0
1 0 1 1 0 0 0 0 0 0
1 0 1 1 0 0 1 1 1 0