AtCoder Beginner Contest 183

A - ReLU

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

ReLU関数は以下のように定義されます。

整数 x が与えられるので ReLU(x) を求めてください。

制約

x は整数
-10 \leq x \leq 10

入力

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

出力

答えを整数で出力せよ。

入力例 1

出力例 1

1 \geq 0 なので ReLU(1) = 1 です。

入力例 2

出力例 2

入力例 3

-1

出力例 3

Score : 100 points

Problem Statement

The function ReLU is defined as follows:

Given an integer x, find ReLU(x).

Constraints

x is an integer.
-10 \leq x \leq 10

Input

Input is given from Standard Input in the following format:

Output

Print the answer as an integer.

Sample Input 1

Sample Output 1

We have 1 \geq 0, so ReLU(1) = 1.

Sample Input 2

Sample Output 2

Sample Input 3

-1

Sample Output 3

B - Billiards

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

高橋君は 2 次元平面上でビリヤードをしています。x 軸は壁になっており、球をぶつけると入射角と反射角が等しくなるように球が跳ね返されます。

いま高橋君の球が (S_x,S_y) にあります。ある座標を狙って球を撞くと、球はその座標へ向かって直線的に転がっていきます。

x 軸で球をちょうど 1 回反射させたのち、(G_x,G_y) を通過させるためには、x 軸のどこを狙えば良いでしょうか？

制約

-10^6 \leq S_x, G_x \leq 10^6
0 < S_y, G_y \leq 10^6
S_x \neq G_x
入力はすべて整数

入力

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

S_x S_y G_x G_y

出力

狙う座標を (x,0) としたときの x を出力せよ。

なお、想定解答との絶対誤差または相対誤差が 10^{-6} 以下であれば正解として扱われる。

入力例 1

1 1 7 2

出力例 1

3.0000000000

図のように (3,0) を狙って球を撞くことで (7,2) を通過させることができます。

入力例 2

1 1 3 2

出力例 2

1.6666666667

入力例 3

-9 99 -999 9999

出力例 3

-18.7058823529

絶対誤差または相対誤差が 10^{-6} 以下のとき正解となります。

Score : 200 points

Problem Statement

Takahashi is playing billiards on a two-dimensional plane. The x-axis functions as a wall; when a ball hits the axis, it will bounce off the axis so that the angle of incidence equals the angle of reflection.

Takahashi's ball is now at (S_x,S_y). When he strikes the ball aiming for some point, it will roll in a straight line towards that point.

To make the ball hit the x-axis exactly once and then pass (G_x, G_y), where along the x-axis should he aim for?

Constraints

-10^6 \leq S_x, G_x \leq 10^6
0 < S_y, G_y \leq 10^6
S_x \neq G_x
All values in input are integers.

Input

Input is given from Standard Input in the following format:

S_x S_y G_x G_y

Output

Let (x, 0) be the point Takahashi should aim for. Print x.

Your output will be considered correct when its absolute or relative error from our answer is at most 10^{-6}.

Sample Input 1

1 1 7 2

Sample Output 1

3.0000000000

As shown below, we can make the ball pass (7, 2) by striking it aiming for (3, 0).

Sample Input 2

1 1 3 2

Sample Output 2

1.6666666667

Sample Input 3

-9 99 -999 9999

Sample Output 3

-18.7058823529

The output will be considered correct when its absolute or relative error from our answer is at most 10^{-6}.

C - Travel

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

N 個の都市があります。都市 i から都市 j へ移動するには T_{i,j} の時間がかかります。

都市 1 を出発し、全ての都市をちょうど 1 度ずつ訪問してから都市 1 に戻るような経路のうち、移動時間の合計がちょうど K になるようなものはいくつありますか？

制約

2\leq N \leq 8
i\neq j のとき 1\leq T_{i,j} \leq 10^8
T_{i,i}=0
T_{i,j}=T_{j,i}
1\leq K \leq 10^9
入力はすべて整数

入力

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

N K
T_{1,1} \ldots T_{1,N}
\vdots
T_{N,1} \ldots T_{N,N}

出力

答えを整数で出力せよ。

入力例 1

4 330
0 1 10 100
1 0 20 200
10 20 0 300
100 200 300 0

出力例 1

都市 1 を出発し、全ての都市をちょうど 1 度ずつ訪問してから都市 1 に戻るような経路は、

1\to 2\to 3\to 4\to 1
1\to 2\to 4\to 3\to 1
1\to 3\to 2\to 4\to 1
1\to 3\to 4\to 2\to 1
1\to 4\to 2\to 3\to 1
1\to 4\to 3\to 2\to 1

の 6 通りがあります。それぞれの移動時間は、421,511,330,511,330,421 なので、ちょうど 330 であるようなものは 2 通りです。

入力例 2

出力例 2

どのような順で都市を訪問しても、移動時間の合計は 5 になります。

Score : 300 points

Problem Statement

There are N cities. The time it takes to travel from City i to City j is T_{i, j}.

Among those paths that start at City 1, visit all other cities exactly once, and then go back to City 1, how many paths take the total time of exactly K to travel along?

Constraints

2\leq N \leq 8
If i\neq j, 1\leq T_{i,j} \leq 10^8.
T_{i,i}=0
T_{i,j}=T_{j,i}
1\leq K \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
T_{1,1} \ldots T_{1,N}
\vdots
T_{N,1} \ldots T_{N,N}

Output

Print the answer as an integer.

Sample Input 1

4 330
0 1 10 100
1 0 20 200
10 20 0 300
100 200 300 0

Sample Output 1

There are six paths that start at City 1, visit all other cities exactly once, and then go back to City 1:

1\to 2\to 3\to 4\to 1
1\to 2\to 4\to 3\to 1
1\to 3\to 2\to 4\to 1
1\to 3\to 4\to 2\to 1
1\to 4\to 2\to 3\to 1
1\to 4\to 3\to 2\to 1

The times it takes to travel along these paths are 421, 511, 330, 511, 330, and 421, respectively, among which two are exactly 330.

Sample Input 2

Sample Output 2

In whatever order we visit the cities, it will take the total time of 5 to travel.

D - Water Heater

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

給湯器が 1 つあり、毎分 W リットルのお湯を供給することができます。

N 人の人がいます。i 番目の人は時刻 S_i から T_i までの間 (時刻 T_i ちょうどを除く)、この湯沸かし器で沸かしたお湯を毎分 P_i リットル使おうと計画しています。お湯はすぐ冷めてしまうので、溜めておくことはできません。

すべての人に計画通りにお湯を供給することはできますか？

制約

1\leq N \leq 2\times 10^5
0\leq S_i < T_i \leq 2\times 10^5
1\leq W, P_i \leq 10^9
入力はすべて整数

入力

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

N W
S_1 T_1 P_1
\vdots
S_N T_N P_N

出力

すべての人に計画通りにお湯を供給することができるなら Yesを、できないなら Noを出力せよ。

入力例 1

出力例 1

No

時刻 3 から 4 の間に、2,3,4 番目の人がそれぞれ毎分 4,6,1 リットル、合計毎分 11 リットルのお湯を使おうとしています。

給湯器は毎分 10 リットルしかお湯を供給することができないので、計画通りに供給することはできません。

入力例 2

出力例 2

Yes

入力例 3

6 1000000000
0 200000 999999999
2 20 1
20 200 1
200 2000 1
2000 20000 1
20000 200000 1

出力例 3

Yes

Score : 400 points

Problem Statement

We have a water heater, which supplies W liters of hot water per minute.

There are N people. The i-th person plans to use P_i liters of hot water per minute boiled by the heater from Time S_i to T_i (excluding at Time T_i exactly). As hot water gets cold fast, it cannot be stored.

Is it possible to supply hot water to the people according to their plans?

Constraints

1\leq N \leq 2\times 10^5
0\leq S_i < T_i \leq 2\times 10^5
1\leq W, P_i \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N W
S_1 T_1 P_1
\vdots
S_N T_N P_N

Output

If it is possible to supply hot water to the people according to their plans, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

No

Between Time 3 and 4, the 2-nd, 3-rd, and 4-th persons plan to use 4, 6, and 1 liter(s) of hot water per minute, for a total of 11 liters per minute.

The water heater can only supply 10 liters of hot water per minute, which is not enough.

Sample Input 2

Sample Output 2

Yes

Sample Input 3

6 1000000000
0 200000 999999999
2 20 1
20 200 1
200 2000 1
2000 20000 1
20000 200000 1

Sample Output 3

Yes

E - Queen on Grid

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

縦 H マス、横 W マスのグリッドがあります。上から i 行目、左から j 列目のマス (i,j) は、S_{ij} が # のとき壁であり、. のとき道です。

マス (1,1) にチェスのクイーンの駒が置いてあります。クイーンの駒は、今いる位置から右・下・右下方向に伸びる直線上にあり、壁を飛び越えずに到達できる道のマスに 1 手で移動することができます。

クイーンの駒がマス (1,1) からマス (H,W) まで移動する方法は何通りありますか？ \bmod (10^9+7) で求めてください。

ただし、移動する方法が異なるとは、ある i が存在して、i 手目の移動の後にクイーンの駒があるマスの位置が異なることを指します。

制約

2 \leq H,W \leq 2000
S_{ij} は # か .
S_{11} と S_{HW} は .

入力

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

H W
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

出力

クイーンの駒がマス (1,1) から (H,W) まで移動する方法の数を \mod (10^9+7) で出力せよ。

入力例 1

3 3
...
.#.
...

出力例 1

移動方法として次の 10 通りが考えられます。

(1,1)\to (1,2)\to (1,3)\to (2,3)\to (3,3)
(1,1)\to (1,2)\to (1,3)\to (3,3)
(1,1)\to (1,2)\to (2,3)\to (3,3)
(1,1)\to (1,3)\to (2,3)\to (3,3)
(1,1)\to (1,3)\to (3,3)
(1,1)\to (2,1)\to (3,1)\to (3,2)\to (3,3)
(1,1)\to (2,1)\to (3,1)\to (3,3)
(1,1)\to (2,1)\to (3,2)\to (3,3)
(1,1)\to (3,1)\to (3,2)\to (3,3)
(1,1)\to (3,1)\to (3,3)

入力例 2

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

出力例 2

(1,1) からは 1 手で (1,2),(1,3),(2,1),(2,2),(3,1),(4,1) のいずれかへ移動することが出来ます。

(4,4) への移動経路として、例えば (1,1)\to (3,1)\to (3,2)\to (4,3)\to (4,4) などがあります。

入力例 3

8 10
..........
..........
..........
..........
..........
..........
..........
..........

出力例 3

13701937

移動方法の数を \bmod (10^9+7) で求めてください。

Score : 500 points

Problem Statement

We have a grid with H horizontal rows and W vertical columns of squares. Square (i,j), which is at the i-th row from the top and j-th column from the left, is wall if S_{ij} is # and road if S_{ij} is ..

There is a queen, the chess piece, at Square (1, 1). In one move, it can move any number of squares to the right, downwards, or diagonally to the lower right to a road square without jumping over wall squares.

In how many ways can the queen travel from Square (1, 1) to Square (H, W)? Find the count modulo (10^9+7).

Here, two ways to travel are considered different if and only if there exists i such that the position of the queen after the i-th move is different in those two ways.

Constraints

2 \leq H,W \leq 2000
S_{ij} is # or ..
S_{11} and S_{HW} are ..

Input

Input is given from Standard Input in the following format:

H W
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the number of ways, modulo (10^9+7), in which the queen can travel from Square (1, 1) to Square (H, W).

Sample Input 1

3 3
...
.#.
...

Sample Output 1

There are 10 ways to travel, as follows:

(1,1)\to (1,2)\to (1,3)\to (2,3)\to (3,3)
(1,1)\to (1,2)\to (1,3)\to (3,3)
(1,1)\to (1,2)\to (2,3)\to (3,3)
(1,1)\to (1,3)\to (2,3)\to (3,3)
(1,1)\to (1,3)\to (3,3)
(1,1)\to (2,1)\to (3,1)\to (3,2)\to (3,3)
(1,1)\to (2,1)\to (3,1)\to (3,3)
(1,1)\to (2,1)\to (3,2)\to (3,3)
(1,1)\to (3,1)\to (3,2)\to (3,3)
(1,1)\to (3,1)\to (3,3)

Sample Input 2

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

Sample Output 2

From (1,1), the queen can move to (1,2), (1,3), (2,1), (2,2), (3,1), or (4,1).

One possible path to (4,4) is (1,1)\to (3,1)\to (3,2)\to (4,3)\to (4,4).

Sample Input 3

8 10
..........
..........
..........
..........
..........
..........
..........
..........

Sample Output 3

13701937

Find the count modulo (10^9+7).

F - Confluence

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 人の生徒が登校しようとしています。生徒 i はクラス C_i に属しています。

各生徒はそれぞれの家から出発したあと、他の生徒と合流を繰り返しながら学校へ向かいます。一度合流した生徒が分かれることはありません。

Q 個のクエリが与えられるので、順番に処理してください。クエリには 2 種類あり、入力形式とクエリの内容は以下の通りです。

1 a b : 生徒 a を含む集団と、生徒 b を含む集団が合流する (既に合流しているときは何も起こらない)
2 x y : クエリの時点で既に生徒 x と合流している生徒(生徒 x を含む)のうち、クラス y に属している生徒の数を求める

制約

1 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
1 \leq C_i,a,b,x,y \leq N
1 a b のクエリにおいて、a \neq b
入力はすべて整数

入力

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

N Q
C_1 \ldots C_N
Query_1
\vdots
Query_Q

出力

2 x y のクエリに対する答えを、1 行に 1 つずつ、順に出力せよ。

入力例 1

出力例 1

2
0

3 番目のクエリの時点で、生徒 1 は、生徒 2,5 と合流しています。生徒 1,2,5 のうちクラス 1 に属する生徒は 2 人です。

5 番目のクエリの時点で、生徒 3 は、生徒 4 と合流しています。生徒 3,4 のうちクラス 4 に属する生徒は 0 人です。

入力例 2

出力例 2

すでに同じ集団に属している生徒に対して、1 a b のクエリが与えられることもあります。

入力例 3

12 9
1 2 3 1 2 3 1 2 3 1 2 3
1 1 2
1 3 4
1 5 6
1 7 8
2 2 1
1 9 10
2 5 6
1 4 8
2 6 1

出力例 3

1
0
0

Score : 600 points

Problem Statement

N students are about to go to school. Student i belongs to Class C_i.

After leaving home, each student will head to school while repeatedly joining up with a group of other students. Once students join up with each other, they will not separate.

You will be given Q queries that should be processed in order. There are two kinds of queries, in the following formats, that mean the following:

1 a b: The group containing Student a and the group containing Student b merges. (If they are already in the same group, nothing happens.)
2 x y: You are asked to find the number of students belonging to Class y who are already in the same group as Student x (including Student x) at the time of this query.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
1 \leq C_i,a,b,x,y \leq N
In a query in the format 1 a b, a \neq b.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
C_1 \ldots C_N
Query_1
\vdots
Query_Q

Output

Print the answers to the queries in the format 2 x y, each in its own line, in order.

Sample Input 1

Sample Output 1

2
0

At the time of the 3-rd query, Student 1 has joined up with Student 2 and 5. Among these three students, two belong to Class 1.

At the time of the 5-th query, Student 3 has joined up with Student 4. Among these two students, none belongs to Class 4.

Sample Input 2

Sample Output 2

There may be queries in the format 1 a b for students who already belong to the same group.

Sample Input 3

12 9
1 2 3 1 2 3 1 2 3 1 2 3
1 1 2
1 3 4
1 5 6
1 7 8
2 2 1
1 9 10
2 5 6
1 4 8
2 6 1

Sample Output 3

1
0
0