AtCoder Daily Training MEDIUM 2024/06/13 18:30start

Please sign in first.

C - Tetrahedral Number

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

整数 N が与えられます。

非負整数の組 (x,y,z) であって x+y+z\leq N を満たすものを辞書順で小さい方から順に全て出力してください。

非負整数の組の辞書順とは？

非負整数の組 (x,y,z) が (x',y',z') より辞書順で小さいとは、下記のいずれかが成り立つことを言います。

x < x' である
x=x' かつ y< y' である
x=x' かつ y=y' かつ z< z' である

制約

0 \leq N \leq 21
N は整数である

入力

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

出力

非負整数の組 (x,y,z) であって x+y+z\leq N を満たすものを、1 行に 1 組ずつ x,y,z を空白区切りで、辞書順で小さい方から順に全て出力せよ。

入力例 1

出力例 1

入力例 2

出力例 2

Score : 150 points

Problem Statement

You are given an integer N.

Print all triples of non-negative integers (x,y,z) such that x+y+z\leq N in ascending lexicographical order.

What is lexicographical order for non-negative integer triples?

A triple of non-negative integers (x,y,z) is said to be lexicographically smaller than (x',y',z') if and only if one of the following holds:

x < x';
x=x' and y< y';
x=x' and y=y' and z< z'.

Constraints

0 \leq N \leq 21
N is an integer.

Input

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

Output

Print all triples of non-negative integers (x,y,z) such that x+y+z\leq N in ascending lexicographical order, with x,y,z separated by spaces, one triple per line.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

D - Longest Segment

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

二次元平面上に N 個の点があります。i 個目の点の座標は (x_i,y_i) です。

この中から 2 個の点を選ぶとき、それらを結ぶ線分の長さの最大値を求めてください。

制約

2 \leq N \leq 100
-1000 \leq x_i,y_i \leq 1000
(x_i,y_i) \neq (x_j,y_j)\ (i \neq j)
入力はすべて整数

入力

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

N
x_1 y_1
x_2 y_2
\hspace{0.4cm} \vdots
x_N y_N

出力

2 点を結ぶ線分の長さの最大値を出力せよ。

想定解との絶対誤差または相対誤差が 10^{-6} 以下であれば正解とみなされる。

入力例 1

出力例 1

1.4142135624

1 個目の点と 3 個目の点を選んだときそれらを結ぶ線分の長さは \sqrt 2 = 1.41421356237\dots となり、これが最大です。

入力例 2

出力例 2

1455.7159750446

Score : 200 points

Problem Statement

There are N points in a two-dimensional plane. The coordinates of the i-th point are (x_i,y_i).

Find the maximum length of a segment connecting two of these points.

Constraints

2 \leq N \leq 100
-1000 \leq x_i,y_i \leq 1000
(x_i,y_i) \neq (x_j,y_j)\ (i \neq j)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
\hspace{0.4cm} \vdots
x_N y_N

Output

Print the maximum length of a segment connecting two of the points.

Your answer will be considered correct when the absolute or relative error from the judge's answer is at most 10^{-6}.

Sample Input 1

Sample Output 1

1.4142135624

For the 1-st and 3-rd points, the length of the segment connecting them is \sqrt 2 = 1.41421356237\dots, which is the maximum length.

Sample Input 2

Sample Output 2

1455.7159750446

E - Final Day

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 人の生徒が 4 日間にわたる試験を受けています。

それぞれの日に行われる試験は 300 点満点です。すなわち、4 日間を通した試験の満点は 1200 点です。

現在 3 日目までの試験が終わり、これから 4 日目の試験が行われようとしています。i \, (1 \leq i \leq N) 番目の生徒は j \, (1 \leq j \leq 3) 日目の試験で P_{i, j} 点獲得しました。

それぞれの生徒について、4 日目の試験後に上位 K 位以内に入っていることがあり得るかどうか判定してください。
ただし、4 日目の試験後の生徒の順位は、その生徒よりも 4 日間の合計点が高い生徒の人数に 1 を加えた値として定めます。

制約

1 \leq K \leq N \leq 10^5
0 \leq P_{i, j} \leq 300 \, (1 \leq i \leq N, 1 \leq j \leq 3)
入力は全て整数である。

入力

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

N K
P_{1,1} P_{1,2} P_{1,3}
\vdots
P_{N,1} P_{N,2} P_{N,3}

出力

N 行出力せよ。i \, (1 \leq i \leq N) 行目には、i 番目の生徒が 4 日目の試験後に上位 K 位以内に入っていることがあり得るならば Yes と、そうでないならば No と出力せよ。

入力例 1

3 1
178 205 132
112 220 96
36 64 20

出力例 1

Yes
Yes
No

4 日目に全員が 100 点を取ると、1 番目の生徒が 1 位になります。 4 日目に 2 番目の生徒が 100 点を取り、それ以外の生徒が 0 点を取ると、2 番目の生徒が 1 位になります。 3 番目の生徒が 1 位になることはあり得ません。

入力例 2

2 1
300 300 300
200 200 200

出力例 2

Yes
Yes

入力例 3

4 2
127 235 78
192 134 298
28 56 42
96 120 250

出力例 3

Yes
Yes
No
Yes

Score : 300 points

Problem Statement

N students are taking a 4-day exam.

There is a 300-point test on each day, for a total of 1200 points.

The first three days of the exam are already over, and the fourth day is now about to begin. The i-th student (1 \leq i \leq N) got P_{i, j} points on the j-th day (1 \leq j \leq 3).

For each student, determine whether it is possible that he/she is ranked in the top K after the fourth day.
Here, the rank of a student after the fourth day is defined as the number of students whose total scores over the four days are higher than that of the student, plus 1.

Constraints

1 \leq K \leq N \leq 10^5
0 \leq P_{i, j} \leq 300 \, (1 \leq i \leq N, 1 \leq j \leq 3)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
P_{1,1} P_{1,2} P_{1,3}
\vdots
P_{N,1} P_{N,2} P_{N,3}

Output

Print N lines. The i-th line (1 \leq i \leq N) should contain Yes if it is possible that the i-th student is ranked in the top K after the fourth day, and No otherwise.

Sample Input 1

3 1
178 205 132
112 220 96
36 64 20

Sample Output 1

Yes
Yes
No

If every student scores 100 on the fourth day, the 1-st student will rank 1-st.
If the 2-nd student scores 100 and the other students score 0 on the fourth day, the 2-nd student will rank 1-st.
The 3-rd student will never rank 1-st.

Sample Input 2

2 1
300 300 300
200 200 200

Sample Output 2

Yes
Yes

Sample Input 3

4 2
127 235 78
192 134 298
28 56 42
96 120 250

Sample Output 3

Yes
Yes
No
Yes

F - Distribution

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 人のすぬけ君が円周上に並んでおり、反時計回りに 1,2,...,N の番号がついています。

i\, (1 \leq i \leq N) 番目のすぬけ君は時刻 t に宝石をもらうと S_i 単位時間後、すなわち時刻 t+S_i にその宝石を (i+1) 番目のすぬけ君に渡します。ただし、(N+1) 番目のすぬけ君とは 1 番目のすぬけ君のことを指すとします。

また、高橋君は時刻 T_i に i 番目のすぬけ君に宝石を渡します。

全ての i\, (1 \leq i \leq N) について、i 番目のすぬけ君が初めて宝石をもらう時刻を求めてください。なお、宝石の受け渡しにかかる時間は無視できるものとします。

制約

1 \leq N \leq 200000
1 \leq S_i,T_i \leq 10^9
入力は全て整数である。

入力

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

N
S_1 S_2 \ldots S_N
T_1 T_2 \ldots T_N

出力

N 行出力せよ。i\, (1 \leq i \leq N) 行目には、i 番目のすぬけ君が初めて宝石をもらう時刻を出力すること。

入力例 1

3
4 1 5
3 10 100

出力例 1

3
7
8

時刻 13 までのすぬけ君と高橋君の行動を時系列順に並べます。

時刻 3 : 高橋君が 1 番目のすぬけ君に宝石を渡します。

時刻 7 : 1 番目のすぬけ君が 2 番目のすぬけ君に宝石を渡します。

時刻 8 : 2 番目のすぬけ君が 3 番目のすぬけ君に宝石を渡します。

時刻 10 : 高橋君が 2 番目のすぬけ君に宝石を渡します。

時刻 11 : 2 番目のすぬけ君が 3 番目のすぬけ君に宝石を渡します。

時刻 13 : 3 番目のすぬけ君が 1 番目のすぬけ君に宝石を渡します。

時刻 14 以降も彼らは宝石の受け渡しを行いますが、答えには影響しません。

入力例 2

4
100 100 100 100
1 1 1 1

出力例 2

S_i や T_i が相異なるとは限らないことに注意してください。

入力例 3

4
1 2 3 4
1 2 4 7

出力例 3

あるすぬけくんが同時刻に複数の宝石の受け渡しをする可能性があること、特に高橋くんとすぬけくんの両方から同時に宝石を貰う可能性があることに注意してください。

入力例 4

8
84 87 78 16 94 36 87 93
50 22 63 28 91 60 64 27

出力例 4

Score : 300 points

Problem Statement

There are N creatures standing in a circle, called Snuke 1, 2, ..., N in counter-clockwise order.

When Snuke i (1 \leq i \leq N) receives a gem at time t, S_i units of time later, it will hand that gem to Snuke i+1 at time t+S_i. Here, Snuke N+1 is Snuke 1.

Additionally, Takahashi will hand a gem to Snuke i at time T_i.

For each i (1 \leq i \leq N), find the time when Snuke i receives a gem for the first time. Assume that it takes a negligible time to hand a gem.

Constraints

1 \leq N \leq 200000
1 \leq S_i,T_i \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
S_1 S_2 \ldots S_N
T_1 T_2 \ldots T_N

Output

Print N lines. The i-th line (1 \leq i \leq N) should contain the time when Snuke i receives a gem for the first time.

Sample Input 1

3
4 1 5
3 10 100

Sample Output 1

3
7
8

We will list the three Snuke's and Takahashi's actions up to time 13 in chronological order.

Time 3: Takahashi hands a gem to Snuke 1.

Time 7: Snuke 1 hands a gem to Snuke 2.

Time 8: Snuke 2 hands a gem to Snuke 3.

Time 10: Takahashi hands a gem to Snuke 2.

Time 11: Snuke 2 hands a gem to Snuke 3.

Time 13: Snuke 3 hands a gem to Snuke 1.

After that, they will continue handing gems, though it will be irrelevant to the answer.

Sample Input 2

4
100 100 100 100
1 1 1 1

Sample Output 2

Note that the values S_i and T_i may not be distinct.

Sample Input 3

4
1 2 3 4
1 2 4 7

Sample Output 3

Note that a Snuke may perform multiple transactions simultaneously. Particularly, a Snuke may receive gems simultaneously from Takahashi and another Snuke.

Sample Input 4

8
84 87 78 16 94 36 87 93
50 22 63 28 91 60 64 27

Sample Output 4

G - Grid Ice Floor

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

N \times M のグリッドがあり、この上にプレイヤーがいます。
このグリッドの上から i 行目、左から j 列目をマス (i,j) と書きます。
このグリッドの各マスは氷か岩であり、その情報は N 個の長さ M の文字列 S_1,S_2,\dots,S_N として与えられます。

もし S_i の j 文字目が . なら、マス (i,j) は氷である。
もし S_i の j 文字目が # なら、マス (i,j) は岩である。

なお、このグリッドの外周 ( 1 行目、 N 行目、 1 列目、 M 列目の全てのマス ) は岩です。

最初、プレイヤーはマス (2,2) の上で停止しています。このマスは氷です。
プレイヤーは以下の行動を 0 度以上何度でも行うことができます。

まず、プレイヤーは上下左右の移動方向を指定する。
その後、プレイヤーは岩のマスにぶつかるまでその方向に移動する。厳密には以下の通りである。
- もし移動方向に隣接するマスが氷なら、そのマスに移動し、同じ方向に移動を継続する。
- もし移動方向に隣接するマスが岩なら、今いるマスに留まり、移動を終了する。

プレイヤーが触れる (通過または上で停止する) ことができる氷の数を求めてください。

制約

3 \le N,M \le 200
S_i は # と . からなる長さ M の文字列
i=1 または i=N または j=1 または j=M であるとき、マス (i,j) は岩
マス (2,2) は氷

入力

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

N M
S_1
S_2
\vdots
S_N

出力

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

入力例 1

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

出力例 1

例えばマス (5,5) には以下のように移動することで上で停止することができます。

(2,2) \rightarrow (5,2) \rightarrow (5,5)

例えばマス (2,4) には以下のように移動することで通過することができます。

(2,2) \rightarrow (2,5) の移動中に (2,4) を通過する。

例えばマス (3,4) は通過することも上で停止することもできません。

入力例 2

21 25
#########################
#..............###...####
#..............#..#...###
#........###...#...#...##
#........#..#..#........#
#...##...#..#..#...#....#
#..#..#..###...#..#.....#
#..#..#..#..#..###......#
#..####..#..#...........#
#..#..#..###............#
#..#..#.................#
#........##.............#
#.......#..#............#
#..........#....#.......#
#........###...##....#..#
#..........#..#.#...##..#
#.......#..#....#..#.#..#
##.......##.....#....#..#
###.............#....#..#
####.................#..#
#########################

出力例 2

Score : 400 points

Problem Statement

There is an N \times M grid and a player standing on it.
Let (i,j) denote the square at the i-th row from the top and j-th column from the left of this grid.
Each square of this grid is ice or rock, which is represented by N strings S_1,S_2,\dots,S_N of length M as follows:

if the j-th character of S_i is ., square (i,j) is ice;
if the j-th character of S_i is #, square (i,j) is rock.

The outer periphery of this grid (all squares in the 1-st row, N-th row, 1-st column, M-th column) is rock.

Initially, the player rests on the square (2,2), which is ice.
The player can make the following move zero or more times.

First, specify the direction of movement: up, down, left, or right.
Then, keep moving in that direction until the player bumps against a rock. Formally, keep doing the following:
- if the next square in the direction of movement is ice, go to that square and keep moving;
- if the next square in the direction of movement is rock, stay in the current square and stop moving.

Find the number of ice squares the player can touch (pass or rest on).

Constraints

3 \le N,M \le 200
S_i is a string of length M consisting of # and ..
Square (i, j) is rock if i=1, i=N, j=1, or j=M.
Square (2,2) is ice.

Input

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

N M
S_1
S_2
\vdots
S_N

Output

Print the answer as an integer.

Sample Input 1

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

Sample Output 1

For instance, the player can rest on (5,5) by moving as follows:

(2,2) \rightarrow (5,2) \rightarrow (5,5).

The player can pass (2,4) by moving as follows:

(2,2) \rightarrow (2,5), passing (2,4) in the process.

The player cannot pass or rest on (3,4).

Sample Input 2

21 25
#########################
#..............###...####
#..............#..#...###
#........###...#...#...##
#........#..#..#........#
#...##...#..#..#...#....#
#..#..#..###...#..#.....#
#..#..#..#..#..###......#
#..####..#..#...........#
#..#..#..###............#
#..#..#.................#
#........##.............#
#.......#..#............#
#..........#....#.......#
#........###...##....#..#
#..........#..#.#...##..#
#.......#..#....#..#.#..#
##.......##.....#....#..#
###.............#....#..#
####.................#..#
#########################