AtCoder Daily Training HARD 2025/02/20 16:30start

E - Cross

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

配点 : 300 点

問題文

縦 H マス横 W マスのグリッドがあります。グリッドの上から i 行目、左から j 列目のマスを (i, j) と呼びます。
グリッドの各マスには # と . のいずれかの文字が書かれています。(i, j) に書かれている文字を C[i][j] とします。また、整数 i, j が 1 \leq i \leq H と 1 \leq j \leq W の少なくとも一方を満たさない場合、 C[i][j] を . と定義します。

正整数 a, b, n が以下の条件を全て満たす時、(a,b) および (a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d) (1 \leq d \leq n) の 4n + 1 マスを (a,b) を中心とするサイズ n のバツ印 と呼びます。

C[a][b] は # である。
1 \leq d \leq n を満たす整数 d について、 C[a+d][b+d],C[a+d][b-d],C[a-d][b+d],C[a-d][b-d] はいずれも # である。
C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1],C[a-n-1][b-n-1] のうち少なくとも 1 つは . である。

例えば次の図で示された例では、(2, 2) を中心とするサイズ 1 のバツ印と (3, 7) を中心とするサイズ 2 のバツ印がグリッド上にあります。

グリッドにはいくつかのバツ印があります。バツ印を構成するマス以外に # は書かれていません。
また、異なるバツ印を構成するマス同士は頂点を共有しません。以下の 2 つのグリッドは異なるバツ印を構成するマス同士が頂点を共有している例で、このようなグリッドの状態は入力として与えられません。 例えば左のグリッドでは (3, 3) と (4, 4) が頂点を共有しているのが条件に反しています。

N = \min(H, W) とします。また、サイズ n のバツ印の個数を S_n とします。S_1, S_2, \dots, S_N を計算してください。

制約

3 \leq H, W \leq 100
C[i][j] は # または .
異なるバツ印を構成するマス同士は頂点を共有しない
H, W は整数

入力

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

H W
C[1][1]C[1][2]\dots C[1][W]
C[2][1]C[2][2]\dots C[2][W]
\vdots
C[H][1]C[H][2]\dots C[H][W]

出力

S_1, S_2, \dots, S_N を空白区切りで出力せよ。

入力例 1

5 9
#.#.#...#
.#...#.#.
#.#...#..
.....#.#.
....#...#

出力例 1

1 1 0 0 0

問題文に書かれた説明の通り、(2, 2) を中心とするサイズ 1 のバツ印と (3, 7) を中心とするサイズ 2 のバツ印が書かれています。

入力例 2

3 3
...
...
...

出力例 2

0 0 0

バツ印が 1 個も書かれていない場合もあります。

入力例 3

3 16
#.#.....#.#..#.#
.#.......#....#.
#.#.....#.#..#.#

出力例 3

3 0 0

入力例 4

15 20
#.#..#.............#
.#....#....#.#....#.
#.#....#....#....#..
........#..#.#..#...
#.....#..#.....#....
.#...#....#...#..#.#
..#.#......#.#....#.
...#........#....#.#
..#.#......#.#......
.#...#....#...#.....
#.....#..#.....#....
........#.......#...
#.#....#....#.#..#..
.#....#......#....#.
#.#..#......#.#....#

出力例 4

5 0 1 0 0 0 1 0 0 0 0 0 0 0 0

Score : 300 points

Problem Statement

We have a grid with H horizontal rows and W vertical columns. We denote by (i, j) the cell at the i-th row from the top and j-th column from the left of the grid.
Each cell in the grid has a symbol # or . written on it. Let C[i][j] be the character written on (i, j). For integers i and j such that at least one of 1 \leq i \leq H and 1 \leq j \leq W is violated, we define C[i][j] to be ..

(4n+1) squares, consisting of (a, b) and (a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d) (1 \leq d \leq n, 1 \leq n), are said to be a cross of size n centered at (a,b) if and only if all of the following conditions are satisfied:

C[a][b] is #.
C[a+d][b+d],C[a+d][b-d],C[a-d][b+d], and C[a-d][b-d] are all #, for all integers d such that 1 \leq d \leq n,
At least one of C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1], and C[a-n-1][b-n-1] is ..

For example, the grid in the following figure has a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).

The grid has some crosses. No # is written on the cells except for those comprising a cross.
Additionally, no two squares that comprise two different crosses share a corner. The two grids in the following figure are the examples of grids where two squares that comprise different crosses share a corner; such grids are not given as an input. For example, the left grid is invalid because (3, 3) and (4, 4) share a corner.

Let N = \min(H, W), and S_n be the number of crosses of size n. Find S_1, S_2, \dots, S_N.

Constraints

3 \leq H, W \leq 100
C[i][j] is # or ..
No two different squares that comprise two different crosses share a corner.
H and W are integers.

Input

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

H W
C[1][1]C[1][2]\dots C[1][W]
C[2][1]C[2][2]\dots C[2][W]
\vdots
C[H][1]C[H][2]\dots C[H][W]

Output

Print S_1, S_2, \dots, and S_N, separated by spaces.

Sample Input 1

5 9
#.#.#...#
.#...#.#.
#.#...#..
.....#.#.
....#...#

Sample Output 1

1 1 0 0 0

As described in the Problem Statement, there are a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).

Sample Input 2

3 3
...
...
...

Sample Output 2

0 0 0

There may be no cross.

Sample Input 3

3 16
#.#.....#.#..#.#
.#.......#....#.
#.#.....#.#..#.#

Sample Output 3

3 0 0

Sample Input 4

15 20
#.#..#.............#
.#....#....#.#....#.
#.#....#....#....#..
........#..#.#..#...
#.....#..#.....#....
.#...#....#...#..#.#
..#.#......#.#....#.
...#........#....#.#
..#.#......#.#......
.#...#....#...#.....
#.....#..#.....#....
........#.......#...
#.#....#....#.#..#..
.#....#......#....#.
#.#..#......#.#....#

Sample Output 4

5 0 1 0 0 0 1 0 0 0 0 0 0 0 0

F - Sort

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

配点 : 300 点

問題文

(1,2,\ldots,N) の並び替えである数列 A=(A_1,\ldots,A_N) が与えられます。
次の操作を 0 回以上 N-1 回以下行うことで、A を (1,2,\ldots,N) にしてください。

操作：1\leq i < j \leq N を満たす整数の組 (i,j) を自由に選ぶ。A の i 番目と j 番目の要素を入れ替える。

なお、制約の条件下で必ず A を (1,2,\ldots,N) にできることが証明できます。

制約

2 \leq N \leq 2\times 10^5
(A_1,\ldots,A_N) は (1,2,\ldots,N) の並び替えである
入力は全て整数である

入力

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

N
A_1 \ldots A_N

出力

操作回数を K として、K+1 行出力せよ。
1 行目には K を出力せよ。
l+1 行目 (1\leq l \leq K) には l 回目の操作で選ぶ整数 i,j を空白区切りで出力せよ。
問題文中の条件を満たすどのような出力も正解とみなされる。

入力例 1

5
3 4 1 2 5

出力例 1

2
1 3
2 4

操作により数列は次のように変化します。

最初 A=(3,4,1,2,5) である。
1 回目の操作で 1 番目の要素と 3 番目の要素を入れ替える。A=(1,4,3,2,5) になる。
2 回目の操作で 2 番目の要素と 4 番目の要素を入れ替える。A=(1,2,3,4,5) になる。

この他、次のような出力でも正解とみなされます。

入力例 2

4
1 2 3 4

出力例 2

入力例 3

3
3 1 2

出力例 3

2
1 2
2 3

Score: 300 points

Problem Statement

You are given a permutation A=(A_1,\ldots,A_N) of (1,2,\ldots,N).
Transform A into (1,2,\ldots,N) by performing the following operation between 0 and N-1 times, inclusive:

Operation: Choose any pair of integers (i,j) such that 1\leq i < j \leq N. Swap the elements at the i-th and j-th positions of A.

It can be proved that under the given constraints, it is always possible to transform A into (1,2,\ldots,N).

Constraints

2 \leq N \leq 2\times 10^5
(A_1,\ldots,A_N) is a permutation of (1,2,\ldots,N).
All input values are integers.

Input

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

N
A_1 \ldots A_N

Output

Let K be the number of operations. Print K+1 lines.
The first line should contain K.
The (l+1)-th line (1\leq l \leq K) should contain the integers i and j chosen for the l-th operation, separated by a space.
Any output that satisfies the conditions in the problem statement will be considered correct.

Sample Input 1

5
3 4 1 2 5

Sample Output 1

2
1 3
2 4

The operations change the sequence as follows:

Initially, A=(3,4,1,2,5).
The first operation swaps the first and third elements, making A=(1,4,3,2,5).
The second operation swaps the second and fourth elements, making A=(1,2,3,4,5).

Other outputs such as the following are also considered correct:

Sample Input 2

4
1 2 3 4

Sample Output 2

Sample Input 3

3
3 1 2

Sample Output 3

2
1 2
2 3

G - K-th Nearest

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

配点 : 425 点

問題文

数直線上に N+Q 個の点 A_1,\dots,A_N,B_1,\dots,B_Q があり、点 A_i の座標は a_i、点 B_j の座標は b_j です。

j=1,2,\dots,Q それぞれについて、以下の問題に答えてください。

点 A_1,A_2,\dots,A_N のうち点 B_j との距離が k_j 番目に近い点を X としたとき、点 X と点 B_j との距離を求めよ。より厳密には、点 A_i と点 B_j との距離を d_i として、(d_1,d_2,\dots,d_N) を昇順に並び替えてできる列を (d_1',d_2',\dots,d_N') としたとき、d_{k_j}' を求めよ。

制約

1\leq N,Q \leq 10^5
-10^8\leq a_i,b_j \leq 10^8
1\leq k_j\leq N
入力は全て整数

入力

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

N Q
a_1 a_2 \dots a_N
b_1 k_1
b_2 k_2
\vdots
b_Q k_Q

出力

Q 行出力せよ。 l\ (1\leq l \leq Q) 行目には、j=l としたときの問題に対する答えを整数として出力せよ。

入力例 1

出力例 1

7
3
13

1 番目のクエリについて説明します。

点 A_1,A_2,A_3,A_4 と点 B_1 との距離は順に 1,1,7,8 なので、点 B_1 との距離が 3 番目に近いのは点 A_3 です。よって、点 A_3 と点 B_1 との距離である 7 を出力します。

入力例 2

出力例 2

0
0

同じ座標に複数の点がある可能性もあります。

入力例 3

10 5
-84 -60 -41 -100 8 -8 -52 -62 -61 -76
-52 5
14 4
-2 6
46 2
26 7

出力例 3

Score : 425 points

Problem Statement

There are N+Q points A_1,\dots,A_N,B_1,\dots,B_Q on a number line, where point A_i has a coordinate a_i and point B_j has a coordinate b_j.

For each j=1,2,\dots,Q, answer the following question:

Let X be the point among A_1,A_2,\dots,A_N that is the k_j-th closest to point B_j. Find the distance between points X and B_j. More formally, let d_i be the distance between points A_i and B_j. Sort (d_1,d_2,\dots,d_N) in ascending order to get the sequence (d_1',d_2',\dots,d_N'). Find d_{k_j}'.

Constraints

1 \leq N, Q \leq 10^5
-10^8 \leq a_i, b_j \leq 10^8
1 \leq k_j \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 \dots a_N
b_1 k_1
b_2 k_2
\vdots
b_Q k_Q

Output

Print Q lines. The l-th line (1 \leq l \leq Q) should contain the answer to the question for j=l as an integer.

Sample Input 1

Sample Output 1

7
3
13

Let us explain the first query.

The distances from points A_1, A_2, A_3, A_4 to point B_1 are 1, 1, 7, 8, respectively, so the 3rd closest to point B_1 is point A_3. Therefore, print the distance between point A_3 and point B_1, which is 7.

Sample Input 2

Sample Output 2

0
0

There may be multiple points with the same coordinates.

Sample Input 3

10 5
-84 -60 -41 -100 8 -8 -52 -62 -61 -76
-52 5
14 4
-2 6
46 2
26 7

Sample Output 3

H - Simultaneous Kagamimochi

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

配点 : 450 点

問題文

N 個の餅が小さいほうから順に並んでいます。 i 番目 (1\leq i\leq N) の餅の大きさは A _ i です。

2 つの餅 A,B の大きさをそれぞれ a,b としたとき、a が b の半分以下であるとき、かつそのときに限り、餅 A を餅 B の上に乗せて鏡餅を 1 つ作ることができます。

同時にいくつの鏡餅を作ることができるか求めてください。

より厳密には、以下ができるような最大の非負整数 K を求めてください。

N 個の餅から 2K 個の餅を選んで K 個の 2 つ組に分け、それぞれの組について一方をもう一方の上に乗せることで鏡餅を K 個作る。

制約

2\leq N\leq 5\times 10 ^ 5
1\leq A _ i\leq 10 ^ 9\ (1\leq i\leq N)
A _ i\leq A _ {i+1}\ (1\leq i\lt N)
入力はすべて整数

入力

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

N
A _ 1 A _ 2 \dotsc A _ N

出力

同時に K 個鏡餅を作れるような最大の K を出力せよ。

入力例 1

6
2 3 4 4 7 10

出力例 1

与えられた餅の大きさは以下のようになっています。

このとき、以下の 3 つの鏡餅を同時に作ることができます。

6 つの餅から 4 つ以上の鏡餅を作ることはできないので、3 を出力してください。

入力例 2

3
387 388 389

出力例 2

鏡餅を 1 つも作ることができない場合もあります。

入力例 3

24
307 321 330 339 349 392 422 430 477 481 488 537 541 571 575 602 614 660 669 678 712 723 785 792

出力例 3

Score : 450 points

Problem Statement

There are N mochi (rice cakes), arranged in ascending order of size. The size of the i-th mochi (1\leq i\leq N) is A_i.

Given two mochi A and B, with sizes a and b respectively, you can make one kagamimochi (a stacked rice cake) by placing mochi A on top of mochi B if and only if a is at most half of b.

Find how many kagamimochi can be made simultaneously.

More precisely, find the maximum non-negative integer K for which the following is possible:

From the N mochi, choose 2K of them to form K pairs. For each pair, place one mochi on top of the other, to make K kagamimochi.

Constraints

2 \leq N \leq 5 \times 10^5
1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
A_i \leq A_{i+1} \ (1 \leq i < N)
All input values are integers.

Input

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

N
A_1 A_2 \dotsc A_N

Output

Print the maximum K such that K kagamimochi can be made simultaneously.

Sample Input 1

6
2 3 4 4 7 10

Sample Output 1

The sizes of the given mochi are as follows:

In this case, you can make the following three kagamimochi simultaneously:

It is not possible to make four or more kagamimochi from six mochi, so print 3.

Sample Input 2

3
387 388 389

Sample Output 2

It is possible that you cannot make any kagamimochi.

Sample Input 3

24
307 321 330 339 349 392 422 430 477 481 488 537 541 571 575 602 614 660 669 678 712 723 785 792

Sample Output 3

I - Rook Score

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

配点 : 500 点

問題文

縦 10^9 マス、横 10^9 マスのマス目があります。上から i 番目、左から j 番目のマスを (i,j) と表記します。

i=1,2,\ldots,N に対し (r_i,c_i) には正整数 x_i が、他の 10^{18}-N 個のマスには 0 が書かれています。

あなたはあるマス (R,C) を選び、 (R,C) と行または列が同じ 2 \times 10^9 - 1 個のマスに書かれた整数の総和 S を求めました。

S として考えられる最大値を求めてください。

制約

1 \leq N \leq 2 \times 10^5
1 \leq r_i,c_i,x_i \leq 10^9
i \neq j ならば (r_i,c_i) \neq (r_j,c_j)
入力はすべて整数

入力

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

N
r_1 c_1 x_1
\vdots
r_N c_N x_N

出力

答えを出力せよ。

入力例 1

出力例 1

(R,C) として (2,2) を選ぶと S が 20 となります。これが最大値です。

入力例 2

1
1 1000000000 1

出力例 2

入力例 3

15
158260522 877914575 602436426
24979445 861648772 623690081
433933447 476190629 262703497
211047202 971407775 628894325
731963982 822804784 450968417
430302156 982631932 161735902
880895728 923078537 707723857
189330739 910286918 802329211
404539679 303238506 317063340
492686568 773361868 125660016
650287940 839296263 462224593
492601449 384836991 191890310
576823355 782177068 404011431
818008580 954291757 160449218
155374934 840594328 164163676

出力例 3

1510053068

Score : 500 points

Problem Statement

We have a grid with 10^9 rows and 10^9 columns. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

For i=1,2,\ldots,N, a positive integer x_i is written on (r_i,c_i). On the other 10^{18}-N squares, 0 is written.

You choose a square (R,C) and compute the sum S of the integers written on the 2 \times 10^9 - 1 squares that share a row or column with (R,C).

Find the maximum possible value of S.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq r_i,c_i,x_i \leq 10^9
(r_i,c_i) \neq (r_j,c_j) if i \neq j.
All values in the input are integers.

Input

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

N
r_1 c_1 x_1
\vdots
r_N c_N x_N

Output

Print the answer.

Sample Input 1

Sample Output 1

If you choose (2,2) as (R,C), then S will be 20, which is the maximum possible value.

Sample Input 2

1
1 1000000000 1

Sample Output 2

Sample Input 3

15
158260522 877914575 602436426
24979445 861648772 623690081
433933447 476190629 262703497
211047202 971407775 628894325
731963982 822804784 450968417
430302156 982631932 161735902
880895728 923078537 707723857
189330739 910286918 802329211
404539679 303238506 317063340
492686568 773361868 125660016
650287940 839296263 462224593
492601449 384836991 191890310
576823355 782177068 404011431
818008580 954291757 160449218
155374934 840594328 164163676

Sample Output 3

1510053068