AtCoder Daily Training HARD 2025/10/09 16:30start

E - Spiral Rotation

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

N 行 N 列のグリッドが与えられます。ここで、N は偶数です。グリッドの上から i 行目、左から j 列目のマスをマス (i, j) と表記します。

グリッドの各マスは黒か白のいずれかで塗られており、A_{i, j} = # のときマス (i, j) は黒、A_{i, j} = . のときマス (i, j) は白で塗られています。

i = 1, 2, \ldots, \frac{N}{2} の順に以下の操作を行った後のグリッドの各マスの色を求めてください。

i 以上 N + 1 - i 以下の整数 x, y について、マス (y, N + 1 - x) の色をマス (x, y) の色で置き換える。この置き換えは条件を満たすすべての整数 x, y について同時に行う。

制約

N は 2 以上 3000 以下の偶数
A_{i, j} は # または .

入力

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

N
A_{1, 1}A_{1, 2}\ldotsA_{1, N}
A_{2, 1}A_{2, 2}\ldotsA_{2, N}
\vdots
A_{N, 1}A_{N, 2}\ldotsA_{N, N}

出力

すべての操作を終えた後、マス (i, j) の色が黒であるとき B_{i, j} = #、マス (i, j) の色が白であるとき B_{i, j} = . として以下の形式で出力せよ。

B_{1, 1}B_{1, 2}\ldotsB_{1, N}
B_{2, 1}B_{2, 2}\ldotsB_{2, N}
\vdots
B_{N, 1}B_{N, 2}\ldotsB_{N, N}

入力例 1

8
.......#
.......#
.####..#
.####..#
.##....#
.##....#
.#######
.#######

出力例 1

........
#######.
#.....#.
#.###.#.
#.#...#.
#.#####.
#.......
########

操作によってグリッドの各マスの色は以下のように変化します。

.......#   ........   ........   ........   ........
.......#   ######..   #######.   #######.   #######.
.####..#   ######..   #....##.   #.....#.   #.....#.
.####..# → ##..##.. → #....##. → #.##..#. → #.###.#.
.##....#   ##..##..   #..####.   #.##..#.   #.#...#.
.##....#   ##......   #..####.   #.#####.   #.#####.
.#######   ##......   #.......   #.......   #.......
.#######   ########   ########   ########   ########

入力例 2

6
.#.#.#
##.#..
...###
###...
..#.##
#.#.#.

出力例 2

#.#.#.
.#.#.#
#.#.#.
.#.#.#
#.#.#.
.#.#.#

入力例 3

12
.......#.###
#...#...#..#
###.#..#####
..#.#.#.#...
.#.....#.###
.......#.#..
#...#..#....
#####.......
...#...#.#.#
..###..#..##
#..#.#.#.#.#
.####.......

出力例 3

.#..##...##.
#.#.#.#.#...
###.##..#...
#.#.#.#.#...
#.#.##...##.
............
............
.###.###.###
...#...#.#..
.###...#.###
...#...#...#
.###...#.###

Score : 400 points

Problem Statement

You are given a grid with N rows and N columns, where N is an even number. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.

Each cell is painted black or white. If A_{i, j} = #, cell (i, j) is black; if A_{i, j} = ., it is white.

Find the color of each cell after performing the following operation for i = 1, 2, \ldots, \frac{N}{2} in this order.

For all pairs of integers x, y between i and N + 1 - i, inclusive, replace the color of cell (y, N + 1 - x) with the color of cell (x, y). Perform these replacements simultaneously for all such pairs x, y.

Constraints

N is an even number between 2 and 3000, inclusive.
Each A_{i, j} is # or ..

Input

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

N
A_{1,1}A_{1,2}\ldots A_{1,N}
A_{2,1}A_{2,2}\ldots A_{2,N}
\vdots
A_{N,1}A_{N,2}\ldots A_{N,N}

Output

After all operations, let B_{i, j} = # if cell (i, j) is black, and B_{i, j} = . if it is white. Print the grid in the following format:

B_{1,1}B_{1,2}\ldots B_{1,N}
B_{2,1}B_{2,2}\ldots B_{2,N}
\vdots
B_{N,1}B_{N,2}\ldots B_{N,N}

Sample Input 1

8
.......#
.......#
.####..#
.####..#
.##....#
.##....#
.#######
.#######

Sample Output 1

........
#######.
#.....#.
#.###.#.
#.#...#.
#.#####.
#.......
########

The operations change the colors of the grid cells as follows:

.......#   ........   ........   ........   ........
.......#   ######..   #######.   #######.   #######.
.####..#   ######..   #....##.   #.....#.   #.....#.
.####..# → ##..##.. → #....##. → #.##..#. → #.###.#.
.##....#   ##..##..   #..####.   #.##..#.   #.#...#.
.##....#   ##......   #..####.   #.#####.   #.#####.
.#######   ##......   #.......   #.......   #.......
.#######   ########   ########   ########   ########

Sample Input 2

6
.#.#.#
##.#..
...###
###...
..#.##
#.#.#.

Sample Output 2

#.#.#.
.#.#.#
#.#.#.
.#.#.#
#.#.#.
.#.#.#

Sample Input 3

12
.......#.###
#...#...#..#
###.#..#####
..#.#.#.#...
.#.....#.###
.......#.#..
#...#..#....
#####.......
...#...#.#.#
..###..#..##
#..#.#.#.#.#
.####.......

Sample Output 3

.#..##...##.
#.#.#.#.#...
###.##..#...
#.#.#.#.#...
#.#.##...##.
............
............
.###.###.###
...#...#.#..
.###...#.###
...#...#...#
.###...#.###

F - NewFolder(1)

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

2 つの文字列 A,B に対して、A の末尾に B を連結した文字列を A+B と表します。

N 個の文字列 S_1,\ldots,S_N が与えられます。i=1,\ldots,N の順に、次の指示に従って加工して出力してください。

S_1,\ldots,S_{i-1} の中に S_i と同じ文字列が存在しないならば、S_i を出力する。
S_1,\ldots,S_{i-1} の中に S_i と同じ文字列が X 個 (X>0) 存在するならば、X を文字列として扱って S_i+ ( +X+ ) を出力する。

制約

1 \leq N \leq 2\times 10^5
S_i は英小文字のみからなる長さ 1 以上 10 以下の文字列

入力

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

N
S_1
S_2
\vdots
S_N

出力

問題文中の指示にしたがって、N 行出力せよ。

入力例 1

5
newfile
newfile
newfolder
newfile
newfolder

出力例 1

newfile
newfile(1)
newfolder
newfile(2)
newfolder(1)

入力例 2

11
a
a
a
a
a
a
a
a
a
a
a

出力例 2

a
a(1)
a(2)
a(3)
a(4)
a(5)
a(6)
a(7)
a(8)
a(9)
a(10)

Score : 300 points

Problem Statement

For two strings A and B, let A+B denote the concatenation of A and B in this order.

You are given N strings S_1,\ldots,S_N. Modify and print them as follows, in the order i=1, \ldots, N:

if none of S_1,\ldots,S_{i-1} is equal to S_i, print S_i;
if X (X>0) of S_1,\ldots,S_{i-1} are equal to S_i, print S_i+ ( +X+ ), treating X as a string.

Constraints

1 \leq N \leq 2\times 10^5
S_i is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S_1
S_2
\vdots
S_N

Output

Print N lines as specified in the Problem Statement.

Sample Input 1

5
newfile
newfile
newfolder
newfile
newfolder

Sample Output 1

newfile
newfile(1)
newfolder
newfile(2)
newfolder(1)

Sample Input 2

11
a
a
a
a
a
a
a
a
a
a
a

Sample Output 2

a
a(1)
a(2)
a(3)
a(4)
a(5)
a(6)
a(7)
a(8)
a(9)
a(10)

G - 1122 Substring

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

正整数からなる（空でも良い）数列 X=(X_1,X_2,\ldots) が以下の 3 つの条件をすべてみたすとき、かつそのときに限り、X を 1122 数列 と呼びます。
（1122 数列の定義はF問題と共通です。）

\lvert X \rvert は偶数である。ここで、\lvert X \rvert は X の長さを表す。
1\leq i\leq \frac{\lvert X \rvert}{2} をみたす整数 i について、X_{2i-1} と X_{2i} は等しい。
各正整数は X に現れないか、ちょうど 2 回現れるかのどちらかである。すなわち、X に含まれる正整数は X にちょうど 2 回ずつ登場する。

正整数からなる長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられるので、A の 連続する部分列 であって、1122 数列であるようなもののうち最長のものの長さを出力してください。

制約

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

入力

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

N
A_1 A_2 \ldots A_N

出力

A の連続する部分列であって、1122 数列であるようなもののうち最長のものの長さを出力せよ。

入力例 1

8
2 3 1 1 2 2 1 1

出力例 1

例えば A の 3 項目から 6 項目までの連続部分列をとると (1,1,2,2) となりますが、これは長さが 4 の 1122 数列となっています。
これより長い部分列であって、1122 数列の条件をみたすようなものは存在しないため、4 を出力します。

入力例 2

3
1 2 2

出力例 2

入力例 3

1
1

出力例 3

項数が 0 の列も 1122 数列の条件をみたしていることに注意してください。

Score : 425 points

Problem Statement

A sequence X = (X_1, X_2, \ldots) of positive integers (possibly empty) is called a 1122 sequence if and only if it satisfies all of the following three conditions: (The definition of a 1122 sequence is the same as in Problem F.)

\lvert X \rvert is even. Here, \lvert X \rvert denotes the length of X.
For each integer i satisfying 1\leq i\leq \frac{|X|}{2}, X_{2i-1} and X_{2i} are equal.
Each positive integer appears in X either not at all or exactly twice. That is, every positive integer contained in X appears exactly twice in X.

Given a sequence A = (A_1, A_2, \ldots, A_N) of length N consisting of positive integers, print the maximum length of a (contiguous) subarray of A that is a 1122 sequence.

Constraints

1\leq N \leq 2 \times 10^5
1\leq A_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 \ldots A_N

Output

Print the maximum length of a (contiguous) subarray of A that is a 1122 sequence.

Sample Input 1

8
2 3 1 1 2 2 1 1

Sample Output 1

For example, taking the subarray from the 3-rd to 6-th elements of A, we get (1, 1, 2, 2), which is a 1122 sequence of length 4.
There is no longer (contiguous) subarray that satisfies the conditions for a 1122 sequence, so the answer is 4.

Sample Input 2

3
1 2 2

Sample Output 2

Sample Input 3

1
1

Sample Output 3

Note that a sequence of length 0 also satisfies the conditions for a 1122 sequence.

H - Prerequisites

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

1 から N までの番号がついた N 冊の本があります。
本 i には C_i 冊の前提となる本があり、そのうち j 冊目は本 P_{i,j} で、本 i を読む前にこの C_i 冊をすべて読む必要があります。
ただし、適切な順序を選ぶことですべての本を読むことができます。

あなたは本 1 を読むために必要な最小の数の本を読もうとしています。
本 1 以外に読まなければならない本の番号を読むべき順に出力してください。ただし、この条件下で読むべき本の集合は一意に定まります。
条件を満たす読む順番が複数考えられる場合は、そのいずれを出力しても構いません。

制約

2 \leq N \leq 2 \times 10^5
0 \leq C_i < N
\sum_{i=1}^{N} C_i \leq 2 \times 10^5
C_1 \geq 1
1 \leq P_{i,j} \leq N
1 \leq j < k \leq C_i のとき P_{i,j} \neq P_{i,k}
すべての本を読むことが可能である

入力

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

N
C_1 P_{1,1} \ldots P_{1,C_1}
C_2 P_{2,1} \ldots P_{2,C_2}
\vdots
C_N P_{N,1} \ldots P_{N,C_N}

出力

本 1 を読むために読む必要のある最小の数の本を読むとき、それらの番号を読むべき順に空白区切りで出力せよ。

入力例 1

出力例 1

5 3 4 2

本 1 を読むために本 2,3,4、本 2 を読むために本 3,5、本 4 を読むために本 5 を読む必要があります。本 3,5,6 を読むために他の本を読む必要はありません。

このとき、例えば本 5,3,4,2 の順に読むことで本 1 を読むことができます。3 冊以下の本を読んだ状態で本 1 が読めるようになることはないため、これは答えの一つです。他にも本 3,5,4,2 の順などで読むことでも 4 冊の本を読んだ状態で本 1 を読むことができるようになります。

入力例 2

出力例 2

6 5 4 3 2

入力例 3

出力例 3

Score : 425 points

Problem Statement

We have N books numbered 1 to N.
Book i assumes that you have read C_i books, the j-th of which is book P_{i,j}: you must read all these C_i books before reading book i.
Here, you can read all the books in some order.

You are trying to read the minimum number of books required to read book 1.
Print the numbers of the books you must read excluding book 1 in the order they should be read. Under this condition, the set of books to read is uniquely determined.
If there are multiple reading orders that satisfy the condition, you may print any of them.

Constraints

2 \leq N \leq 2 \times 10^5
0 \leq C_i < N
\sum_{i=1}^{N} C_i \leq 2 \times 10^5
C_1 \geq 1
1 \leq P_{i,j} \leq N
P_{i,j} \neq P_{i,k} for 1 \leq j < k \leq C_i.
It is possible to read all the books.

Input

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

N
C_1 P_{1,1} \ldots P_{1,C_1}
C_2 P_{2,1} \ldots P_{2,C_2}
\vdots
C_N P_{N,1} \ldots P_{N,C_N}

Output

Print the numbers of the books you must read to read book 1 in the order they should be read, with spaces in between.

Sample Input 1

Sample Output 1

5 3 4 2

To read book 1, you must read books 2,3,4; to read book 2, you must read books 3,5; to read book 4, you must read book 5. To read books 3,5,6, you do not have to read any other books.

For example, if you read books 5,3,4,2 in this order, you can read book 1. This is a correct answer, because you will never be able to read book 1 with three or fewer books read. As another example, reading books 3,5,4,2 in this order also allows you to read book 1 with 4 books read.

Sample Input 2

Sample Output 2

6 5 4 3 2

Sample Input 3

Sample Output 3

I - Main Street

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

xy 平面上にある AtCoder 王国の道路は、全ての整数 n に対する直線 x=n および直線 y=n からなります。そのうち、全ての整数 n に対する直線 x=Bn および直線 y=Bn は大通りです。

高橋君は (x,y) にいるときに、(x,y-1),(x,y+1),(x+1,y),(x-1,y) のいずれかに移動することができます。また、1 回の移動につき、大通りに沿って移動する場合は 1 秒、それ以外の場合は K 秒かかります。

(S_x,S_y) にいる高橋君が (G_x,G_y) に移動するのに最短で何秒かかるかを求めてください。

この問題は T ケース与えられます。

制約

1 \le T \le 2 \times 10^5
1 \le B,K \le 10^9
0 \le S_x,S_y,G_x,G_y \le 10^9
入力はすべて整数。

入力

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

T
\mathrm{testcase}_1
\mathrm{testcase}_2
\vdots
\mathrm{testcase}_T

それぞれのテストケースは以下の形式で与えられる。

B K S_x S_y G_x G_y

出力

T 行出力せよ。i 行目には i 個目のテストケースの解を出力せよ。

入力例 1

4
3 4 2 2 4 4
5 6 2 3 2 3
1 1000000000 0 0 1000000000 1000000000
1000000000 1000000000 500000000 500000000 1000000000 1000000000

出力例 1

10
0
2000000000
500000000500000000

1 個目のテストケースについて、(2,2) から (2,3) に 4 秒かけて移動し、(2,3) から (4,3) に 2 秒かけて移動し、(4,3) から (4,4) に 4 秒かけて移動することで 10 秒で (2,2) から (4,4) に移動することができます。10 秒より早く移動することはできないため、解は 10 です。
2 個目のテストケースについて、初めから (G_x,G_y) にいるため解は 0 です。

入力例 2

10
928184439 674654465 203937094 186855052 851783856 805293696
55480262 448852233 823161539 786348805 550018803 322680316
891870741 235679524 32164572 497841190 620600021 96487871
321502816 428964257 499656016 521484999 717623189 824784374
144040837 680268887 76238777 371138006 350230937 78690135
768922620 799628518 403830696 60449731 218880692 88319939
482031503 121412614 472330444 284479575 949635609 427232765
389524418 132987043 656496997 678732442 23028233 488463974
857778764 629964237 714551548 739330018 579247790 874251485
461612428 535402609 555160129 833592114 44418273 287363785

出力例 2

177606591118701316
6205925075792263
30320747646118343
84136273267803188
83764071874751489
118960470930399064
2929499649126153
16403238161749820
84995699148879437
71771264361119335

Score : 500 points

Problem Statement

The roads in the Kingdom of AtCoder, which lies on the xy-plane, are the lines x=n and y=n for all integers n. Among them, the lines x=Bn and y=Bn for all integers n are main roads.

When Takahashi is at (x,y), he can move to (x,y-1), (x,y+1), (x+1,y), or (x-1,y). Each move takes 1 second along a main road and K seconds otherwise.

Find the minimum number of seconds Takahashi needs to get from (S_x, S_y) to (G_x, G_y).

You will have T test cases to solve.

Constraints

1 \le T \le 2 \times 10^5
1 \le B,K \le 10^9
0 \le S_x,S_y,G_x,G_y \le 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

T
\mathrm{testcase}_1
\mathrm{testcase}_2
\vdots
\mathrm{testcase}_T

Each test case is in the following format:

B K S_x S_y G_x G_y

Output

Print T lines. The i-th line should contain the answer to the i-th test case.

Sample Input 1

4
3 4 2 2 4 4
5 6 2 3 2 3
1 1000000000 0 0 1000000000 1000000000
1000000000 1000000000 500000000 500000000 1000000000 1000000000

Sample Output 1

10
0
2000000000
500000000500000000

For the 1-st test case, he can go from (2,2) to (2,3) in 4 seconds, from (2,3) to (4,3) in 2 seconds, and from (4,3) to (4,4) in 4 seconds to get from (2,2) to (4,4) in 10 seconds. It is impossible to get there in less than 10 seconds, so the answer is 10.
For the 2-nd test case, he is already at (G_x, G_y) in the beginning, so the answer is 0.

Sample Input 2

10
928184439 674654465 203937094 186855052 851783856 805293696
55480262 448852233 823161539 786348805 550018803 322680316
891870741 235679524 32164572 497841190 620600021 96487871
321502816 428964257 499656016 521484999 717623189 824784374
144040837 680268887 76238777 371138006 350230937 78690135
768922620 799628518 403830696 60449731 218880692 88319939
482031503 121412614 472330444 284479575 949635609 427232765
389524418 132987043 656496997 678732442 23028233 488463974
857778764 629964237 714551548 739330018 579247790 874251485
461612428 535402609 555160129 833592114 44418273 287363785

Sample Output 2

177606591118701316
6205925075792263
30320747646118343
84136273267803188
83764071874751489
118960470930399064
2929499649126153
16403238161749820
84995699148879437
71771264361119335