TOYOTA SYSTEMS Programming Contest 2023(AtCoder Beginner Contest 330)

A - Counting Passes

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

N 人の人 1,2,\dots,N がある試験を受け、人 i は A_i 点を取りました。
この試験では、 L 点以上を取った人のみが合格となります。
N 人のうち何人が合格したか求めてください。

制約

入力は全て整数
1 \le N \le 100
1 \le L \le 1000
0 \le A_i \le 1000

入力

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

N L
A_1 A_2 \dots A_N

出力

答えを整数として出力せよ。

入力例 1

5 60
60 20 100 90 40

出力例 1

5 人が試験を受けました。 60 点以上取ると合格です。

人 1 は 60 点を取ったので、合格です。
人 2 は 20 点を取ったので、不合格です。
人 3 は 100 点を取ったので、合格です。
人 4 は 90 点を取ったので、合格です。
人 5 は 40 点を取ったので、不合格です。

以上より、合格したのは 3 人だと分かります。

入力例 2

4 80
79 78 77 76

出力例 2

合格者がいない場合もあります。

入力例 3

10 50
31 41 59 26 53 58 97 93 23 84

出力例 3

Score : 100 points

Problem Statement

N people labeled 1,2,\dots,N took an exam, and person i scored A_i points.
Only those who scored at least L points pass this exam.
Determine how many people out of the N have passed the exam.

Constraints

All input values are integers.
1 \le N \le 100
1 \le L \le 1000
0 \le A_i \le 1000

Input

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

N L
A_1 A_2 \dots A_N

Output

Print the answer as an integer.

Sample Input 1

5 60
60 20 100 90 40

Sample Output 1

Five people took the exam. You need to score at least 60 points to pass.

Person 1 scored 60 points, so they passed.
Person 2 scored 20 points, so they did not pass.
Person 3 scored 100 points, so they passed.
Person 4 scored 90 points, so they passed.
Person 5 scored 40 points, so they did not pass.

From the above, we can see that three people have passed.

Sample Input 2

4 80
79 78 77 76

Sample Output 2

There may be cases no one has passed.

Sample Input 3

10 50
31 41 59 26 53 58 97 93 23 84

Sample Output 3

B - Minimize Abs 1

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) 及び整数 L,R が与えられます。ここで L,R は L\leq R を満たします。

i=1,2,\ldots,N について以下の 2 つの条件を共に満たす整数 X_i を求めてください。なお、求める整数は常に一意に定まります。

L\leq X_i \leq R
L 以上 R 以下であるようなどの整数 Y についても |X_i - A_i| \leq |Y-A_i| を満たす

制約

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

入力

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

N L R
A_1 \ldots A_N

出力

i=1,2,\ldots,N について X_i を空白区切りで出力せよ。

入力例 1

5 4 7
3 1 4 9 7

出力例 1

4 4 4 7 7

i=1 では、

|4-3|=1
|5-3|=2
|6-3|=3
|7-3|=4

より X_i = 4 です。

入力例 2

3 10 10
11 10 9

出力例 2

10 10 10

Score : 200 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N and integers L and R such that L\leq R.

For each i=1,2,\ldots,N, find the integer X_i that satisfies both of the following conditions. Note that the integer to be found is always uniquely determined.

L\leq X_i \leq R.
For every integer Y such that L \leq Y \leq R, it holds that |X_i - A_i| \leq |Y - A_i|.

Constraints

1\leq N\leq 2\times 10^5
1\leq L\leq R \leq 10^9
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 L R
A_1 \ldots A_N

Output

Print X_i for i=1,2,\ldots,N, separated by spaces.

Sample Input 1

5 4 7
3 1 4 9 7

Sample Output 1

4 4 4 7 7

For i=1:

|4-3|=1
|5-3|=2
|6-3|=3
|7-3|=4

Thus, X_i = 4.

Sample Input 2

3 10 10
11 10 9

Sample Output 2

10 10 10

C - Minimize Abs 2

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

正整数 D が与えられます。

非負整数 x,y に対する |x^2+y^2-D| の最小値を求めてください。

制約

1\leq D \leq 2\times 10^{12}
入力は全て整数

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

x=4,y=2 のとき |x^2+y^2-D| = |16+4-21|=1 となります。

|x^2+y^2-D|=0 を満たすような非負整数 x,y は存在しないので、答えは 1 です。

入力例 2

998244353

出力例 2

入力例 3

264428617

出力例 3

Score : 300 points

Problem Statement

You are given a positive integer D.

Find the minimum value of |x^2+y^2-D| for non-negative integers x and y.

Constraints

1\leq D \leq 2\times 10^{12}
All input values are integers.

Input

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

Output

Print the answer.

Sample Input 1

Sample Output 1

For x=4 and y=2, we have |x^2+y^2-D| = |16+4-21|=1.

There are no non-negative integers x and y such that |x^2+y^2-D|=0, so the answer is 1.

Sample Input 2

998244353

Sample Output 2

Sample Input 3

264428617

Sample Output 3

D - Counting Ls

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

N \times N のマス目が与えられます。このうち上から i 行目、左から j 列目のマスを (i,j) と書きます。
各マスの状態を表す N 個の長さ N の文字列 S_1,S_2,\dots,S_N が以下の形式で与えられます。

S_i の j 文字目が o であるとき、 (i,j) には o が書かれている。
S_i の j 文字目が x であるとき、 (i,j) には x が書かれている。

以下の条件を全て満たすマスの三つ組の個数を求めてください。

組に含まれる 3 マスは相異なる。
3 マス全てに o が書かれている。
マスのうち、丁度 2 つが同じ行にある。
マスのうち、丁度 2 つが同じ列にある。

但し、ふたつの三つ組は、丁度一方に含まれるマスが存在する場合のみ区別します。

制約

N は 2 以上 2000 以下の整数
S_i は長さ N の o と x からなる文字列

入力

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

N
S_1
S_2
\vdots
S_N

出力

答えを整数として出力せよ。

入力例 1

3
ooo
oxx
xxo

出力例 1

以下の 4 つの三つ組が条件を満たします。

(1,1),(1,2),(2,1)
(1,1),(1,3),(2,1)
(1,1),(1,3),(3,3)
(1,2),(1,3),(3,3)

入力例 2

4
oxxx
xoxx
xxox
xxxo

出力例 2

入力例 3

15
xooxxooooxxxoox
oxxoxoxxxoxoxxo
oxxoxoxxxoxoxxx
ooooxooooxxoxxx
oxxoxoxxxoxoxxx
oxxoxoxxxoxoxxo
oxxoxooooxxxoox
xxxxxxxxxxxxxxx
xooxxxooxxxooox
oxxoxoxxoxoxxxo
xxxoxxxxoxoxxoo
xooxxxooxxoxoxo
xxxoxxxxoxooxxo
oxxoxoxxoxoxxxo
xooxxxooxxxooox

出力例 3

Score : 400 points

Problem Statement

You are given an N \times N grid. Let (i,j) denote the cell in the i-th row from the top and the j-th column from the left.
The states of the cells are given by N strings of length N, S_1, S_2, \dots, S_N, in the following format:

If the j-th character of S_i is o, there is an o written in cell (i,j).
If the j-th character of S_i is x, there is an x written in cell (i,j).

Find the number of triples of cells that satisfy all of the following conditions:

The three cells in the triple are distinct.
All three cells have an o written in them.
Exactly two of the cells are in the same row.
Exactly two of the cells are in the same column.

Here, two triples are considered different if and only if some cell is contained in exactly one of the triples.

Constraints

N is an integer between 2 and 2000, inclusive.
S_i is a string of length N consisting of o and x.

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print the answer as an integer.

Sample Input 1

3
ooo
oxx
xxo

Sample Output 1

The following four triples satisfy the conditions:

(1,1),(1,2),(2,1)
(1,1),(1,3),(2,1)
(1,1),(1,3),(3,3)
(1,2),(1,3),(3,3)

Sample Input 2

4
oxxx
xoxx
xxox
xxxo

Sample Output 2

Sample Input 3

15
xooxxooooxxxoox
oxxoxoxxxoxoxxo
oxxoxoxxxoxoxxx
ooooxooooxxoxxx
oxxoxoxxxoxoxxx
oxxoxoxxxoxoxxo
oxxoxooooxxxoox
xxxxxxxxxxxxxxx
xooxxxooxxxooox
oxxoxoxxoxoxxxo
xxxoxxxxoxoxxoo
xooxxxooxxoxoxo
xxxoxxxxoxooxxo
oxxoxoxxoxoxxxo
xooxxxooxxxooox

Sample Output 3

E - Mex and Update

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 475 点

問題文

長さ N の数列 A=(A_1,A_2,\dots,A_N) が与えられます。
以下の Q 個のクエリに、与えられる順番で対応してください。

k 番目のクエリは以下の形式で与えられます。

i_k x_k

まず、 A_{i_k} = x_k と変更する。この変更は以降のクエリにも引き継がれる。
その後、 A の \rm{mex} を出力する。
- A の \rm{mex} とは、 A に含まれない最小の非負整数を指す。

制約

入力は全て整数
1 \le N,Q \le 2 \times 10^5
0 \le A_i \le 10^9
1 \le i_k \le N
0 \le x_k \le 10^9

入力

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

N Q
A_1 A_2 \dots A_N
i_1 x_1
i_2 x_2
\vdots
i_Q x_Q

出力

全体で Q 行出力せよ。
そのうち k 行目には k 番目のクエリに対する答えを整数として出力せよ。

入力例 1

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

出力例 1

最初、数列 A は (2,0,2,2,1,1,2,5) です。
この入力では、 5 つのクエリを処理します。

1 番目のクエリで A_4 = 3 と変更し、 A=(2,0,2,3,1,1,2,5) となりました。
- この時点で、 A の \rm{mex} は 4 です。
2 番目のクエリで A_4 = 4 と変更し、 A=(2,0,2,4,1,1,2,5) となりました。
- この時点で、 A の \rm{mex} は 3 です。
3 番目のクエリで A_6 = 3 と変更し、 A=(2,0,2,4,1,3,2,5) となりました。
- この時点で、 A の \rm{mex} は 6 です。
4 番目のクエリで A_8 = 1000000000 と変更し、 A=(2,0,2,4,1,3,2,1000000000) となりました。
- この時点で、 A の \rm{mex} は 5 です。
5 番目のクエリで A_2 = 1 と変更し、 A=(2,1,2,4,1,3,2,1000000000) となりました。
- この時点で、 A の \rm{mex} は 0 です。

Score : 475 points

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_N) of length N.
Respond to the following Q queries in the order they are given.

The k-th query is given in the following format:

i_k x_k

First, change A_{i_k} to x_k. This change will carry over to subsequent queries.
Then, print the \rm{mex} of A.
- The \rm{mex} of A is the smallest non-negative integer not contained in A.

Constraints

All input values are integers.
1 \le N,Q \le 2 \times 10^5
0 \le A_i \le 10^9
1 \le i_k \le N
0 \le x_k \le 10^9

Input

Input is given from Standard Input in the following format:

N Q
A_1 A_2 \dots A_N
i_1 x_1
i_2 x_2
\vdots
i_Q x_Q

Output

Print Q lines in total.
The k-th line should contain the answer to the k-th query as an integer.

Sample Input 1

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

Sample Output 1

Initially, the sequence A is (2,0,2,2,1,1,2,5).
This input gives you five queries.

The first query changes A_4 to 3, making A=(2,0,2,3,1,1,2,5).
- At this point, the \rm{mex} of A is 4.
The second query changes A_4 to 4, making A=(2,0,2,4,1,1,2,5).
- At this point, the \rm{mex} of A is 3.
The third query changes A_6 to 3, making A=(2,0,2,4,1,3,2,5).
- At this point, the \rm{mex} of A is 6.
The fourth query changes A_8 to 1000000000, making A=(2,0,2,4,1,3,2,1000000000).
- At this point, the \rm{mex} of A is 5.
The fifth query changes A_2 to 1, making A=(2,1,2,4,1,3,2,1000000000).
- At this point, the \rm{mex} of A is 0.

F - Minimize Bounding Square

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 525 点

問題文

xy 平面上に N 個の点 1,2,\dots,N があります。このうち点 i は座標 (X_i,Y_i) にあります。
あなたは、以下の操作を 0 回以上 K 回以下行うことができます。

まず、 N 点の中からひとつを選択する。選ばれた点を k とし、この点が現在 (x,y) にあるものとする。
次に、以下の 4 つからひとつを選択し、実行する。
- 点 k を x 軸沿いに +1 だけ移動させる。点 k の座標は (x+1,y) となる。
- 点 k を x 軸沿いに -1 だけ移動させる。点 k の座標は (x-1,y) となる。
- 点 k を y 軸沿いに +1 だけ移動させる。点 k の座標は (x,y+1) となる。
- 点 k を y 軸沿いに -1 だけ移動させる。点 k の座標は (x,y-1) となる。
複数の点を同じ座標に存在させることも許されます。また、入力で複数の点が同じ座標に存在しうることに注意してください。

全ての操作が終わった後、 N 個全ての点を内部または周上に包含する、各辺が x 軸または y 軸に平行な正方形をひとつ書き込みます。
このとき、書き込む正方形の一辺の長さとしてありうる最小の値を求めてください。全ての点が常に格子点にあることから、この値は整数であることが示せます。

特に、全ての点を同じ座標に存在させられる時、答えは 0 であるものとします。

制約

入力は全て整数
1 \le N \le 2 \times 10^5
0 \le K \le 4 \times 10^{14}
0 \le X_i,Y_i \le 10^9

入力

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

N K
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

答えを整数として出力せよ。

入力例 1

出力例 1

このケースについて、横を x 軸、縦を y 軸として図示したものが以下です。

例えば、図中の矢印に従って 4 度の移動を行った後、図中に示した一辺が 3 の正方形で全ての点を内部または周上に含むことができ、これが最小値であることが示せます。

入力例 2

4 400000000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

出力例 2

最初から全ての点が同じ座標に存在します。
例えば操作を 0 回行う (即ち、全く行わない) ことにより、全ての点を同じ座標に存在させられるので、この入力に対する答えは 0 です。

入力例 3

10 998244353
489733278 189351894
861289363 30208889
450668761 133103889
306319121 739571083
409648209 922270934
930832199 304946211
358683490 923133355
369972904 539399938
915030547 735320146
386219602 277971612

出力例 3

484373824

Score : 525 points

Problem Statement

There are N points labeled 1, 2, \dots, N on the xy-plane. Point i is located at coordinates (X_i, Y_i).
You can perform the following operation between 0 and K times, inclusive.

First, choose one of the N points. Let k be the selected point, and assume it is currently at (x, y).
Next, choose and execute one of the following four actions:
- Move point k along the x-axis by +1. The coordinates of point k become (x+1, y).
- Move point k along the x-axis by -1. The coordinates of point k become (x-1, y).
- Move point k along the y-axis by +1. The coordinates of point k become (x, y+1).
- Move point k along the y-axis by -1. The coordinates of point k become (x, y-1).
It is allowed to have multiple points at the same coordinates. Note that the input may already have multiple points at the same coordinates.

After all your operations, draw one square that includes all the N points inside or on the circumference, with each side parallel to the x- or y-axis.
Find the minimum possible value for the length of a side of this square. This value can be shown to be an integer since all points are always on lattice points.

In particular, if all points can be made to exist at the same coordinates, the answer is considered to be 0.

Constraints

All input values are integers.
1 \le N \le 2 \times 10^5
0 \le K \le 4 \times 10^{14}
0 \le X_i, Y_i \le 10^9

Input

Input is given from Standard Input in the following format:

N K
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

Output

Print the answer as an integer.

Sample Input 1

Sample Output 1

The figure below illustrates this case with the horizontal x-axis and the vertical y-axis.

For example, after performing four moves following the arrows in the figure, you can include all points inside or on the circumference of the square shown in the figure with a side length of 3, and this can be shown to be the minimum value.

Sample Input 2

4 400000000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

Sample Output 2

All points already exist at the same coordinates from the beginning.
For example, by performing zero operations, all points can be made to exist at the same coordinates, so the answer for this input is 0.

Sample Input 3

10 998244353
489733278 189351894
861289363 30208889
450668761 133103889
306319121 739571083
409648209 922270934
930832199 304946211
358683490 923133355
369972904 539399938
915030547 735320146
386219602 277971612

Sample Output 3

484373824

G - Inversion Squared

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 625 点

問題文

長さ N の数列 A = (A_1,\ldots,A_N) が与えられます。 A の各要素は -1 または 1 以上 N 以下の整数で、かつ 1 から N までの整数はそれぞれ高々 1 個含まれます。

(1,\ldots,N) の順列 P=(P_1,\ldots,P_N) であって、 A_i \neq -1 \Rightarrow P_i = A_i を満たすものを 良い順列 と呼びます。良い順列全てに対する、転倒数の二乗の総和を 998244353 で割ったあまりを求めてください。

なお、順列 P の転倒数は、 1\leq i < j \leq N と P_i > P_j を共に満たすような整数の組 (i,j) の個数です。

制約

1\leq N\leq 3000
1\leq A_i \leq N または A_i = -1
A に 1,\ldots,N はそれぞれ高々 1 個含まれる
入力は全て整数

入力

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

N 
A_1 \ldots A_N

出力

答えを出力せよ。

入力例 1

4
3 -1 2 -1

出力例 1

良い順列は P=(3,1,2,4) と P=(3,4,2,1) の 2 つで、転倒数はそれぞれ 2 と 5 です。

よって答えは 2^2 + 5^2 = 29 となります。

入力例 2

10
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

出力例 2

952235647

入力例 3

15
-1 -1 10 -1 -1 -1 2 -1 -1 3 -1 -1 -1 -1 1

出力例 3

460544744

998244353 で割ったあまりを求めてください。

Score : 625 points

Problem Statement

You are given a sequence A = (A_1,\ldots,A_N) of length N. Each element of A is either -1 or an integer between 1 and N, and each integer from 1 to N is contained at most once.

A permutation P=(P_1,\ldots,P_N) of (1,\ldots,N) is called a good permutation if and only if it satisfies A_i \neq -1 \Rightarrow P_i = A_i. Find the sum of the squares of the inversion numbers of all good permutations, modulo 998244353.

The inversion number of a permutation P is the number of pairs of integers (i,j) such that 1\leq i < j \leq N and P_i > P_j.

Constraints

1\leq N\leq 3000
A_i = -1 or 1\leq A_i \leq N.
Each integer from 1 to N is contained at most once in A.
All input values are integers.

Input

Input is given from Standard Input in the following format:

N 
A_1 \ldots A_N

Output

Print the answer.

Sample Input 1

4
3 -1 2 -1

Sample Output 1

There are two good permutations: P=(3,1,2,4) and P=(3,4,2,1), with inversion numbers 2 and 5, respectively.

Thus, the answer is 2^2 + 5^2 = 29.

Sample Input 2

10
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

Sample Output 2

952235647

Sample Input 3

15
-1 -1 10 -1 -1 -1 2 -1 -1 3 -1 -1 -1 -1 1

Sample Output 3

460544744

Find the sum modulo 998244353.