Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
東西に真っ直ぐ延びる道路があり、東向きを正とする座標により道路上の位置を表します。
高橋君の家は座標 0、スーパーは座標 A、駅は座標 B にあります。ここで、高橋君の家、スーパー、駅の座標はそれぞれ相異なります。
高橋君の家を基準としてスーパーと駅が同じ方向にあるならば Yes を、そうでないならば No を出力してください。
制約
- -100 \leq A, B \leq 100
- A \neq 0
- B \neq 0
- A \neq B
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
問題文中の指示にしたがって Yes、No のいずれかを出力せよ。
入力例 1
40 -20
出力例 1
No
高橋君の家を基準としてスーパーと駅は反対の方向にあります。
入力例 2
-3 -5
出力例 2
Yes
入力例 3
9 19
出力例 3
Yes
Score : 100 points
Problem Statement
There is a road that runs straight east and west, and positions on the road are represented by coordinates whose positive direction is east.
Takahashi's house is at coordinate 0, the supermarket is at coordinate A, and the station is at coordinate B. Here, the coordinates of Takahashi's house, the supermarket, and the station are pairwise distinct.
Print Yes if the supermarket and the station are in the same direction from Takahashi's house, and No otherwise.
Constraints
- -100 \leq A, B \leq 100
- A \neq 0
- B \neq 0
- A \neq B
- All input values are integers.
Input
The input is given from Standard Input in the following format:
A B
Output
Print Yes or No according to the instructions in the problem statement.
Sample Input 1
40 -20
Sample Output 1
No
The supermarket and the station are in opposite directions from Takahashi's house.
Sample Input 2
-3 -5
Sample Output 2
Yes
Sample Input 3
9 19
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
ある水槽には N 個の蛇口 1,2,\dots,N と、M 個の排水管 1,2,\dots,M が付いています。 N 個の蛇口と M 個の排水管のうち、ちょうど 1 つが詰まっています。
o と x からなる長さ M の文字列 S_1,S_2,\dots,S_N が与えられます。
蛇口 i から水を注いだとき、排水管 j から水が出てくる(すなわち、蛇口 i と排水管 j がいずれも詰まっていない)ならば S_i の j 文字目は o であり、そうでないとき x です。
N 個の蛇口と M 個の排水管のうちどれが詰まっているかを特定してください。 ただし、答えがちょうど 1 つに特定できるような入力が与えられることは保証されます。
制約
- 2 \leq N \leq 100
- 2 \leq M \leq 100
- N と M は整数
- S_i は
oとxからなる長さ M の文字列 - 答えがちょうど 1 つに特定できる
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 S_2 \vdots S_N
出力
答えを 1 行で出力せよ。
詰まっているのが蛇口 i ならば Faucet と i を空白区切りで出力せよ。
詰まっているのが排水管 j ならば Drain と j を空白区切りで出力せよ。
入力例 1
3 4 oooo xxxx oooo
出力例 1
Faucet 2
蛇口 2 が詰まっています。
入力例 2
4 3 oxo oxo oxo oxo
出力例 2
Drain 2
入力例 3
2 2 xo xo
出力例 3
Drain 1
Score : 200 points
Problem Statement
A water tank has N faucets 1,2,\dots,N and M drains 1,2,\dots,M. Exactly one of the N faucets and M drains is clogged.
You are given N strings S_1,S_2,\dots,S_N, each of length M and consisting of o and x.
The j-th character of S_i is o if water comes out of drain j when water is poured from faucet i (that is, neither faucet i nor drain j is clogged), and x otherwise.
Identify which of the N faucets and M drains is clogged. It is guaranteed that the answer can be uniquely determined from the input.
Constraints
- 2 \leq N \leq 100
- 2 \leq M \leq 100
- N and M are integers.
- S_i is a string of length M consisting of
oandx. - The answer can be uniquely determined.
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 in one line.
If faucet i is clogged, print Faucet and i separated by a space.
If drain j is clogged, print Drain and j separated by a space.
Sample Input 1
3 4 oooo xxxx oooo
Sample Output 1
Faucet 2
Faucet 2 is clogged.
Sample Input 2
4 3 oxo oxo oxo oxo
Sample Output 2
Drain 2
Sample Input 3
2 2 xo xo
Sample Output 3
Drain 1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
数直線上の座標 1, 2, \ldots, N に 1 個ずつ点があり、座標 i にある点を点 i と呼びます。
各点には色がついており、点 i の色は C_i です。ただし、C_1, C_2, \ldots, C_N に現れる値は 2 種類以上あります。
各 i = 1, 2, \ldots, N について、点 i と異なる色の点のうち、点 i からの距離が最も短いものまでの距離を求めてください。
制約
- 2 \leq N \leq 3 \times 10^5
- 1 \leq C_i \leq N
- C_1, C_2, \ldots, C_N に現れる値は 2 種類以上
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N C_1 C_2 \ldots C_N
出力
i = 1, 2, \ldots, N に対する答えをこの順に空白区切りで出力せよ。
入力例 1
6 1 1 2 3 3 3
出力例 1
2 1 1 1 2 3
点 1 と異なる色の点のうち、点 1 から最も近い点は点 3 であり、点 1 からの距離は 2 です。
点 2 と異なる色の点のうち、点 2 から最も近い点は点 3 であり、点 2 からの距離は 1 です。
点 3 と異なる色の点のうち、点 3 から最も近い点は点 2 と点 4 であり、点 3 からの距離は 1 です。
点 4 と異なる色の点のうち、点 4 から最も近い点は点 3 であり、点 4 からの距離は 1 です。
点 5 と異なる色の点のうち、点 5 から最も近い点は点 3 であり、点 5 からの距離は 2 です。
点 6 と異なる色の点のうち、点 6 から最も近い点は点 3 であり、点 6 からの距離は 3 です。
したがって、2, 1, 1, 1, 2, 3 をこの順に空白区切りで出力します。
入力例 2
7 4 2 3 3 3 4 4
出力例 2
1 1 1 2 1 1 2
Score : 300 points
Problem Statement
There is one point at each of the coordinates 1, 2, \ldots, N on a number line, and the point at coordinate i is called point i.
Each point has a color, and the color of point i is C_i. Here, at least two distinct values appear in C_1, C_2, \ldots, C_N.
For each i = 1, 2, \ldots, N, find the distance from point i to the nearest point whose color is different from that of point i.
Constraints
- 2 \leq N \leq 3 \times 10^5
- 1 \leq C_i \leq N
- At least two distinct values appear in C_1, C_2, \ldots, C_N.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N C_1 C_2 \ldots C_N
Output
Print the answers for i = 1, 2, \ldots, N in this order, separated by spaces.
Sample Input 1
6 1 1 2 3 3 3
Sample Output 1
2 1 1 1 2 3
Among the points whose color is different from that of point 1, the nearest to point 1 is point 3, and its distance from point 1 is 2.
Among the points whose color is different from that of point 2, the nearest to point 2 is point 3, and its distance from point 2 is 1.
Among the points whose color is different from that of point 3, the nearest to point 3 are points 2 and 4, and their distance from point 3 is 1.
Among the points whose color is different from that of point 4, the nearest to point 4 is point 3, and its distance from point 4 is 1.
Among the points whose color is different from that of point 5, the nearest to point 5 is point 3, and its distance from point 5 is 2.
Among the points whose color is different from that of point 6, the nearest to point 6 is point 3, and its distance from point 6 is 3.
Thus, print 2, 1, 1, 1, 2, 3 in this order, separated by spaces.
Sample Input 2
7 4 2 3 3 3 4 4
Sample Output 2
1 1 1 2 1 1 2
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
A, B, C からなる長さ N の文字列 S が与えられます。
S を 2 箇所で区切り、3 つの空でない部分文字列に分割します。形式的には、S の k 文字目を S_k とし、1 \leq i < j < N なる整数の組 (i, j) を選び、S を S_1S_2 \ldots S_i, S_{i + 1}S_{i + 2} \ldots S_j, S_{j + 1}S_{j + 2} \ldots S_N の 3 つの部分文字列に分割します。
3 つの部分文字列それぞれが A, B, C をすべて含むような区切り方の個数を求めてください。
制約
- 3 \leq N \leq 3 \times 10^5
- N は整数
- S は
A,B,Cからなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
答えを出力せよ。
入力例 1
12 AABCCABCCBCA
出力例 1
5
| により文字列を区切る位置を表すことにすると、AABC|CAB|CCBCA, AABC|CABC|CBCA, AABC|CABCC|BCA, AABCC|ABC|CBCA, AABCC|ABCC|BCA の 5 通りの区切り方があります。
入力例 2
3 ABC
出力例 2
0
入力例 3
20 BCACABCACACABCAACBCA
出力例 3
65
Score : 400 points
Problem Statement
You are given a string S of length N consisting of A, B, and C.
We split S at two positions to divide it into three non-empty substrings. Formally, let S_k denote the k-th character of S; we choose a pair of integers (i, j) such that 1 \leq i < j < N, and divide S into three substrings S_1S_2 \ldots S_i, S_{i + 1}S_{i + 2} \ldots S_j, and S_{j + 1}S_{j + 2} \ldots S_N.
Find the number of ways to split S such that each of the three substrings contains all of A, B, and C.
Constraints
- 3 \leq N \leq 3 \times 10^5
- N is an integer.
- S is a string of length N consisting of
A,B, andC.
Input
The input is given from Standard Input in the following format:
N S
Output
Print the answer.
Sample Input 1
12 AABCCABCCBCA
Sample Output 1
5
Using | to denote the positions where the string is split, there are five ways to split it: AABC|CAB|CCBCA, AABC|CABC|CBCA, AABC|CABCC|BCA, AABCC|ABC|CBCA, and AABCC|ABCC|BCA.
Sample Input 2
3 ABC
Sample Output 2
0
Sample Input 3
20 BCACABCACACABCAACBCA
Sample Output 3
65
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
N 個の都市と M 本の一方通行の道路があります。i 本目の道路は都市 U_i から都市 V_i へ通じ、色 C_i で塗られています。
あなたは、道路を通ることを繰り返して都市 1 から都市 N まで移動したいです。ただし、同じ色で塗られた道路を 2 回続けて通ってはいけません。
都市 1 から都市 N に辿り着くことができるか判定し、辿り着くことができる場合は道路を通る回数として考えられる最小値を求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq U_i, V_i \leq N
- U_i \neq V_i
- 1 \leq C_i \leq M
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M U_1 V_1 C_1 U_2 V_2 C_2 \vdots U_M V_M C_M
出力
都市 1 から都市 N に辿り着くことができない場合は -1 と出力せよ。そうでない場合は、道路を通る回数として考えられる最小値を出力せよ。
入力例 1
6 10 1 2 1 2 4 2 2 5 2 3 6 5 4 3 3 5 2 3 5 3 2 5 6 2 6 1 3 6 5 3
出力例 1
4
i 本目の道路を道路 i と表記すると、道路 1, 2, 5, 4 の順で道路を通ることで都市 6 に辿り着くことができます。
入力例 2
3 5 1 2 1 1 2 1 1 2 2 1 2 2 1 2 3
出力例 2
-1
入力例 3
8 10 1 2 1 2 3 2 2 4 1 3 2 3 4 5 2 4 6 1 5 4 3 6 7 2 6 8 1 7 6 3
出力例 3
10
Score : 450 points
Problem Statement
There are N cities and M one-way roads. The i-th road leads from city U_i to city V_i and is painted in color C_i.
You want to travel from city 1 to city N by repeatedly traversing roads. However, you must not traverse roads painted in the same color twice in a row.
Determine whether it is possible to reach city N from city 1, and if it is possible, find the minimum possible number of times you traverse a road.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq U_i, V_i \leq N
- U_i \neq V_i
- 1 \leq C_i \leq M
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M U_1 V_1 C_1 U_2 V_2 C_2 \vdots U_M V_M C_M
Output
If it is impossible to reach city N from city 1, print -1. Otherwise, print the minimum possible number of times you traverse a road.
Sample Input 1
6 10 1 2 1 2 4 2 2 5 2 3 6 5 4 3 3 5 2 3 5 3 2 5 6 2 6 1 3 6 5 3
Sample Output 1
4
Let road i denote the i-th road. You can reach city 6 by traversing roads 1, 2, 5, 4 in this order.
Sample Input 2
3 5 1 2 1 1 2 1 1 2 2 1 2 2 1 2 3
Sample Output 2
-1
Sample Input 3
8 10 1 2 1 2 3 2 2 4 1 3 2 3 4 5 2 4 6 1 5 4 3 6 7 2 6 8 1 7 6 3
Sample Output 3
10
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
N 個の商品 1,2,\dots,N が 1 個ずつあります。 商品 i の料金は c_i で価値は v_i です。
高橋君が橋を 1 回渡るたびに、料金が 1 以上であるようなすべての商品の料金が 1 下がります。
j=0,1,\dots,M について、以下の値を求めてください。
- 高橋君が橋を j 回渡った後、料金の合計が M 以下になるように 0 個以上の商品を選ぶとき、選んだ商品の価値の合計としてあり得る最大値
制約
- 1 \leq N \leq 10^2
- 1 \leq c_i \leq M \leq 10^4
- 1 \leq v_i \leq 10^9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M c_1 v_1 c_2 v_2 \vdots c_N v_N
出力
答えを合計 M+1 行で出力せよ。 k 行目には、j=k-1 のときの答えを出力せよ。
入力例 1
3 4 1 3 2 5 4 8
出力例 1
8 16 16 16 16
j=0 のとき、すべての商品の料金は最初のままです。商品 1,2 を選ぶと、価値の合計を 8 にすることができ、またこれがあり得る最大値です。
j=1 のとき、すべての商品の料金は 1 下がります。商品 1,2,3 を選ぶと、価値の合計を 16 にすることができ、またこれがあり得る最大値です。
入力例 2
5 6 4 6 4 7 6 11 2 4 1 2
出力例 2
11 17 24 30 30 30 30
入力例 3
2 1 1 4 1 7
出力例 3
7 11
Score : 525 points
Problem Statement
There are N items 1,2,\dots,N, one of each. Item i has a price of c_i and a value of v_i.
Each time Takahashi crosses a bridge, the price of every item whose price is at least 1 decreases by 1.
For each j=0,1,\dots,M, find the following value.
- The maximum possible total value of the chosen items when, after Takahashi has crossed the bridge j times, zero or more items are chosen so that their total price is at most M.
Constraints
- 1 \leq N \leq 10^2
- 1 \leq c_i \leq M \leq 10^4
- 1 \leq v_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M c_1 v_1 c_2 v_2 \vdots c_N v_N
Output
Print the answers in M+1 lines in total. The k-th line should contain the answer for j=k-1.
Sample Input 1
3 4 1 3 2 5 4 8
Sample Output 1
8 16 16 16 16
For j=0, the prices of all items remain as they were initially. Choosing items 1 and 2 makes the total value 8, which is the maximum possible.
For j=1, the prices of all items decrease by 1. Choosing items 1, 2, and 3 makes the total value 16, which is the maximum possible.
Sample Input 2
5 6 4 6 4 7 6 11 2 4 1 2
Sample Output 2
11 17 24 30 30 30 30
Sample Input 3
2 1 1 4 1 7
Sample Output 3
7 11
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 625 点
問題文
長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
以下の条件をすべて満たすような 3 整数の組 (a,b,c) の総数を求めてください。
- 0 \leq a \lt b \lt c \leq N
- b-a=c-b
- A_{a+i} \neq A_{b+i} を満たす 1 以上 b-a 以下の整数 i がちょうど 1 つ存在する
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
答えを 1 行で出力せよ。
入力例 1
7 1 2 1 3 1 2 1
出力例 1
10
条件を満たす (a,b,c) は (0,1,2),(0,2,4),(1,2,3),(1,3,5),(2,3,4),(2,4,6),(3,4,5),(3,5,7),(4,5,6),(5,6,7) の 10 個です。
入力例 2
2 1000000000 1000000000
出力例 2
0
入力例 3
6 1 2 3 1 2 4
出力例 3
6
Score : 625 points
Problem Statement
You are given a sequence of positive integers A=(A_1,A_2,\dots,A_N) of length N.
Find the number of triples of integers (a,b,c) that satisfy all of the following conditions.
- 0 \leq a \lt b \lt c \leq N
- b-a=c-b
- There is exactly one integer i between 1 and b-a, inclusive, such that A_{a+i} \neq A_{b+i}.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 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 A_1 A_2 \ldots A_N
Output
Print the answer in one line.
Sample Input 1
7 1 2 1 3 1 2 1
Sample Output 1
10
The triples (a,b,c) that satisfy the conditions are the following ten: (0,1,2),(0,2,4),(1,2,3),(1,3,5),(2,3,4),(2,4,6),(3,4,5),(3,5,7),(4,5,6),(5,6,7).
Sample Input 2
2 1000000000 1000000000
Sample Output 2
0
Sample Input 3
6 1 2 3 1 2 4
Sample Output 3
6