AtCoder Daily Training HARD 2024/08/14 20:00start

E - Shapes

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

2 次元グリッド上に 2 つの図形 S と T があります。グリッドは正方形のマスからなります。

S は N 行 N 列のグリッド内にあり、S_{i,j} が # であるようなマス全体からなります。
T も N 行 N 列のグリッド内にあり、T_{i,j} が # であるようなマス全体からなります。

S と T を 90 度回転及び平行移動の繰り返しによって一致させることができるか判定してください。

制約

1 \leq N \leq 200
S,T は # と . のみからなる
S,T は 1 つ以上 # を含む

入力

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

N
S_{1,1}S_{1,2}\ldots S_{1,N}
\vdots
S_{N,1}S_{N,2}\ldots S_{N,N}
T_{1,1}T_{1,2}\ldots T_{1,N}
\vdots
T_{N,1}T_{N,2}\ldots T_{N,N}

出力

S と T を90 度回転及び平行移動の繰り返しによって一致させることができるとき Yes を、そうでないとき No を出力せよ。

入力例 1

5
.....
..#..
.###.
.....
.....
.....
.....
....#
...##
....#

出力例 1

Yes

S を左回りに 90 度回転させ、平行移動することで T に一致させることができます。

入力例 2

5
#####
##..#
#..##
#####
.....
#####
#..##
##..#
#####
.....

出力例 2

No

90 度回転と平行移動の繰り返しによって一致させることはできません。

入力例 3

4
#...
..#.
..#.
....
#...
#...
..#.
....

出力例 3

Yes

S 及び T は連結とは限りません。

入力例 4

4
#...
.##.
..#.
....
##..
#...
..#.
....

出力例 4

No

回転や移動の操作は連結成分ごとにできるわけではなく、S,T 全体に対して行うことに注意してください。

Score : 300 points

Problem Statement

We have two figures S and T on a two-dimensional grid with square cells.

S lies within a grid with N rows and N columns, and consists of the cells where S_{i,j} is #.
T lies within the same grid with N rows and N columns, and consists of the cells where T_{i,j} is #.

Determine whether it is possible to exactly match S and T by 90-degree rotations and translations.

Constraints

1 \leq N \leq 200
Each of S and T consists of # and ..
Each of S and T contains at least one #.

Input

Input is given from Standard Input in the following format:

N
S_{1,1}S_{1,2}\ldots S_{1,N}
\vdots
S_{N,1}S_{N,2}\ldots S_{N,N}
T_{1,1}T_{1,2}\ldots T_{1,N}
\vdots
T_{N,1}T_{N,2}\ldots T_{N,N}

Output

Print Yes if it is possible to exactly match S and T by 90-degree rotations and translations, and No otherwise.

Sample Input 1

5
.....
..#..
.###.
.....
.....
.....
.....
....#
...##
....#

Sample Output 1

Yes

We can match S to T by rotating it 90-degrees counter-clockwise and translating it.

Sample Input 2

5
#####
##..#
#..##
#####
.....
#####
#..##
##..#
#####
.....

Sample Output 2

No

It is impossible to match them by 90-degree rotations and translations.

Sample Input 3

4
#...
..#.
..#.
....
#...
#...
..#.
....

Sample Output 3

Yes

Each of S and T may not be connected.

Sample Input 4

4
#...
.##.
..#.
....
##..
#...
..#.
....

Sample Output 4

No

Note that it is not allowed to rotate or translate just a part of a figure; it is only allowed to rotate or translate a whole figure.

F - 1 2 1 3 1 2 1

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

列 S_n を次のように定義します。

S_1 は 1 つの 1 からなる長さ 1 の列である。
S_n (n は 2 以上の整数) は S_{n-1}, n, S_{n-1} をこの順につなげた列である。

たとえば S_2,S_3 は次のような列です。

S_2 は S_1, 2, S_1 をこの順につなげた列なので 1,2,1 である。
S_3 は S_2, 3, S_2 をこの順につなげた列なので 1,2,1,3,1,2,1 である。

N が与えられるので、列 S_N をすべて出力してください。

制約

N は整数
1 \leq N \leq 16

入力

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

出力

S_N を空白区切りで出力せよ。

入力例 1

出力例 1

1 2 1

問題文の説明にある通り、S_2 は 1,2,1 となります。

入力例 2

出力例 2

入力例 3

出力例 3

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

S_4 は S_3,4,S_3 をこの順につなげた列です。

Score : 300 points

Problem Statement

We define sequences S_n as follows.

S_1 is a sequence of length 1 containing a single 1.
S_n (n is an integer greater than or equal to 2) is a sequence obtained by concatenating S_{n-1}, n, S_{n-1} in this order.

For example, S_2 and S_3 is defined as follows.

S_2 is a concatenation of S_1, 2, and S_1, in this order, so it is 1,2,1.
S_3 is a concatenation of S_2, 3, and S_2, in this order, so it is 1,2,1,3,1,2,1.

Given N, print the entire sequence S_N.

Constraints

N is an integer.
1 \leq N \leq 16

Input

Input is given from Standard Input in the following format:

Output

Print S_N, with spaces in between.

Sample Input 1

Sample Output 1

1 2 1

As described in the Problem Statement, S_2 is 1,2,1.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

S_4 is a concatenation of S_3, 4, and S_3, in this order.

G - Pyramid

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

正の整数 k について、サイズ k の ピラミッド数列 とは、長さ (2k-1) の数列であって各項の値が順に 1,2,\ldots,k-1,k,k-1,\ldots,2,1 であるようなものをさします。

長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
A に対して、次の操作のうち一方を選んで行うことを繰り返して (0 回でも良い) 得ることのできるピラミッド数列のサイズの最大値を求めてください。

数列の項を 1 つ選び、その項の値を 1 減少させる。
先頭または末尾の項を削除する。

なお、問題の制約のもとで、操作を繰り返すことで必ず 1 種類以上のピラミッド数列を得ることができることが証明できます。

制約

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

入力

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

N
A_1 A_2 \ldots A_N

出力

数列 A に問題文の操作を繰り返して得ることのできるピラミッド数列のサイズの最大値を出力せよ。

入力例 1

5
2 2 3 1 1

出力例 1

A=(2,2,3,1,1) から始めて、次のようにして数列 A からサイズ 2 のピラミッド数列を作る事ができます。

第 3 項を選び、1 減少させる。数列は A=(2,2,2,1,1) となる。
先頭を削除する。数列は A=(2,2,1,1) となる。
末尾を削除する。数列は A=(2,2,1) となる。
第 1 項を選び、1 減少させる。数列は A=(1,2,1) となる。

(1,2,1) はサイズ 2 のピラミッド数列です。
一方、どのように操作を行ってもサイズ 3 以上のピラミッド数列を作ることはできないため 2 を出力します。

入力例 2

5
1 2 3 4 5

出力例 2

入力例 3

1
1000000000

出力例 3

Score: 400 points

Problem Statement

For a positive integer k, the Pyramid Sequence of size k is a sequence of length (2k-1) where the terms of the sequence have the values 1,2,\ldots,k-1,k,k-1,\ldots,2,1 in this order.

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N.
Find the maximum size of a Pyramid Sequence that can be obtained by repeatedly choosing and performing one of the following operations on A (possibly zero times).

Choose one term of the sequence and decrease its value by 1.
Remove the first or last term.

It can be proved that the constraints of the problem guarantee that at least one Pyramid Sequence can be obtained by repeating the operations.

Constraints

1\leq N\leq 2\times 10^5
1\leq A_i\leq 10^9
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 maximum size of the Pyramid Sequence that can be obtained by repeatedly performing the operations described in the problem statement on the sequence A.

Sample Input 1

5
2 2 3 1 1

Sample Output 1

Starting with A=(2,2,3,1,1), you can create a Pyramid Sequence of size 2 as follows:

Choose the third term and decrease it by 1. The sequence becomes A=(2,2,2,1,1).
Remove the first term. The sequence becomes A=(2,2,1,1).
Remove the last term. The sequence becomes A=(2,2,1).
Choose the first term and decrease it by 1. The sequence becomes A=(1,2,1).

(1,2,1) is a Pyramid Sequence of size 2.
On the other hand, there is no way to perform the operations to create a Pyramid Sequence of size 3 or larger, so you should print 2.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

Sample Input 3

1
1000000000

Sample Output 3

H - Colorful Subsequence

実行時間制限: 5 sec / メモリ制限: 1024 MiB

配点 : 525 点

問題文

N 個のボールが左右一列に並んでいます。
左から i (1\leq i\leq N) 番目のボールは色 C_i で、価値は V_i です。

高橋君はこの列から ちょうど K 個のボールを取り除いたうえで、残ったボールを元の順番で並べたときに同じ色のボールが隣り合わないようにしたいと考えています。また、その条件のもとで、列に残ったボールの価値の総和をなるべく大きくしたいと考えています。

高橋君が、残ったボールの列において同じ色のボールが隣り合わないように K 個のボールを取り除くことができるか判定し、できる場合は列に残ったボールの価値の総和としてあり得る最大の値を求めてください。

制約

1\leq K<N\leq 2\times 10^5
K\leq 500
1\leq C_i\leq N
1\leq V_i\leq 10^9
入力はすべて整数

入力

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

N K
C_1 V_1
C_2 V_2
\vdots
C_N V_N

出力

高橋君が同じ色のボールが隣り合わないようにK 個のボールを取り除くことができる場合は、列に残ったボールの価値の総和としてあり得る最大値を整数で出力せよ。できない場合は、-1 を出力せよ。

入力例 1

出力例 1

左から、3,5 番目のボールを取り除くと、残ったボールは左から順に色 1,3,1 であるため、どの隣り合う 2 つのボールの色も異なり、条件をみたしています。
このとき、列に残ったボールの価値の和は V_1+V_2+V_4=1+5+4=10 です。
他にも 5 つのボールから 2 つのボールを取り除く方法であって、同じ色のボールが隣り合わないようにできるものは存在しますが、 3,5 番目のボールを取り除いた時に残ったボールの価値の和は最大となります。

よって、10 を出力します。

入力例 2

出力例 2

-1

どのようにボールを 1 つ取り除いても色 1 のボールが隣り合ってしまいます。
よって、 -1 を出力します。

入力例 3

出力例 3

必ずちょうど K 個のボールを取り除く必要があることに注意してください。

Score: 525 points

Problem Statement

There are N balls lined up in a row.
The i-th ball from the left is of color C_i and has a value of V_i.

Takahashi wants to remove exactly K balls from this row so that no two adjacent balls have the same color when arranging the remaining balls without changing the order. Additionally, under that condition, he wants to maximize the total value of the balls remaining in the row.

Determine if Takahashi can remove K balls so that no two adjacent balls in the remaining row have the same color. If it is possible, find the maximum possible total value of the remaining balls.

Constraints

1\leq K<N\leq 2\times 10^5
K\leq 500
1\leq C_i\leq N
1\leq V_i\leq 10^9
All input values are integers.

Input

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

N K
C_1 V_1
C_2 V_2
\vdots
C_N V_N

Output

If Takahashi can remove K balls so that no two adjacent balls in the remaining row have the same color, print the maximum possible total value of the remaining balls as an integer. Otherwise, print -1.

Sample Input 1

Sample Output 1

After removing the 3-rd and 5-th balls from the left, the remaining balls are of colors 1, 3, 1 from left to right, so no two adjacent balls have the same color, satisfying the condition.
The total value of the remaining balls is V_1+V_2+V_4=1+5+4=10.
There are other ways to remove two balls from the five balls so that no two adjacent balls have the same color, but the total value of the remaining balls is maximized when removing the 3-rd and 5-th balls.

Hence, print 10.

Sample Input 2

Sample Output 2

-1

No matter how you remove one ball, balls of color 1 will end up next to each other.
Hence, print -1.

Sample Input 3

Sample Output 3

Note that exactly K balls must be removed.

I - Swap and Sort

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

(1,2,\ldots,N) を並び替えた長さ N の順列 P=(P_1,P_2,\ldots,P_N) があります。

あなたが可能な操作は M 種類あり、操作 i は「 P の a_i 番目の要素と P の b_i 番目の要素を入れ替える」というものです。

操作を好きな順序で、合計 5\times 10^5 回以下行うことによって、P を昇順に並び替えることはできますか？

できるならば、操作手順を 1 つ教えてください。できないならばその旨を伝えてください。

制約

2\leq N \leq 1000
P は (1,2,\ldots,N) を並び替えた順列
1\leq M \leq \min(2\times 10^5, \frac{N(N-1)}{2})
1\leq a_i \lt b_i\leq N
i\neq j ならば (a_i,b_i)\neq (a_j,b_j)
入力に含まれる値は全て整数

入力

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

N
P_1 P_2 \ldots P_N
M
a_1 b_1
a_2 b_2
\vdots
a_M b_M

出力

P を昇順に並び替えることができるならば以下の形式で出力せよ。

K
c_1 c_2 \ldots c_K

ここで、K は操作の回数を表し、c_i(1\leq i \leq K) は i 回目に行う操作が操作 c_i であることを表す。
0\leq K \leq 5\times 10^5 を満たさなければならないことに注意せよ。

P を昇順に並び替えることができないならば、-1 と出力せよ。

入力例 1

6
5 3 2 4 6 1
4
1 5
5 6
1 2
2 3

出力例 1

3
4 2 1

P は、(5,3,2,4,6,1)\to (5,2,3,4,6,1)\to (5,2,3,4,1,6)\to (1,2,3,4,5,6) と変化します。

入力例 2

出力例 2

-1

P を昇順に並び替えることはできません。

入力例 3

出力例 3

初めから P が昇順に並んでいることもあります。

また、以下のような答えも正解になります。

4
5 5 5 5

操作の回数を最小化する必要はないことに注意してください。

Score : 500 points

Problem Statement

We have a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).

There are M kinds of operations available to you. Operation i swaps the a_i-th and b_i-th elements of P.

Is it possible to sort P in ascending order by doing at most 5\times 10^5 operations in total in any order?

If it is possible, give one such sequence of operations. Otherwise, report so.

Constraints

2\leq N \leq 1000
P is a permutation of (1,2,\ldots,N).
1\leq M \leq \min(2\times 10^5, \frac{N(N-1)}{2})
1\leq a_i \lt b_i\leq N
(a_i,b_i)\neq (a_j,b_j) if i\neq j.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
P_1 P_2 \ldots P_N
M
a_1 b_1
a_2 b_2
\vdots
a_M b_M

Output

If it is possible to sort P in ascending order, print the following:

K
c_1 c_2 \ldots c_K

Here, K represents the number of operations to do, and c_i (1\leq i \leq K) means the i-th operation to do is Operation c_i.
Note that 0\leq K \leq 5\times 10^5 must hold.

If it is impossible to sort P in ascending order, print -1.

Sample Input 1

6
5 3 2 4 6 1
4
1 5
5 6
1 2
2 3

Sample Output 1

3
4 2 1

P changes as follows: (5,3,2,4,6,1)\to (5,2,3,4,6,1)\to (5,2,3,4,1,6)\to (1,2,3,4,5,6).

Sample Input 2

Sample Output 2

-1

We cannot sort P in ascending order.

Sample Input 3

Sample Output 3

P may already be sorted in ascending order.

Additionally, here is another accepted output:

4
5 5 5 5

Note that it is not required to minimize the number of operations.