Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
りんご市場に N 人の売り手と M 人の買い手がいます。
i 番目の売り手は、A_i 円以上でならりんごを売ってもよいと考えています。
i 番目の買い手は、B_i 円以下でならりんごを買ってもよいと考えています。
次の条件を満たすような最小の整数 X を求めてください。
条件：りんごを X 円で売ってもよいと考える売り手の人数が、りんごを X 円で買ってもよいと考える買い手の人数以上である。
制約
- 1 \leq N,M \leq 2\times 10^5
- 1\leq A_i,B_i \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 \ldots A_N B_1 \ldots B_M
出力
答えを出力せよ。
入力例 1
3 4 110 90 120 100 80 120 10000
出力例 1
110
りんごを 110 円で売ってもよいと考える売り手は 1,2 番目の 2 人であり、りんごを 110 円で買ってもよいと考える買い手は 3,4 番目の 2 人であるため、110 は条件を満たします。
110 未満の整数が条件を満たすことはないため、これが答えです。
入力例 2
5 2 100000 100000 100000 100000 100000 100 200
出力例 2
201
入力例 3
3 2 100 100 100 80 120
出力例 3
100
Score : 300 points
Problem Statement
There are N sellers and M buyers in an apple market.
The i-th seller may sell an apple for A_i yen or more (yen is the currency in Japan).
The i-th buyer may buy an apple for B_i yen or less.
Find the minimum integer X that satisfies the following condition.
Condition: The number of people who may sell an apple for X yen is greater than or equal to the number of people who may buy an apple for X yen.
Constraints
- 1 \leq N,M \leq 2\times 10^5
- 1\leq A_i,B_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 \ldots A_N B_1 \ldots B_M
Output
Print the answer.
Sample Input 1
3 4 110 90 120 100 80 120 10000
Sample Output 1
110
Two sellers, the 1-st and 2-nd, may sell an apple for 110 yen; two buyers, the 3-rd and 4-th, may buy an apple for 110 yen. Thus, 110 satisfies the condition.
Since an integer less than 110 does not satisfy the condition, this is the answer.
Sample Input 2
5 2 100000 100000 100000 100000 100000 100 200
Sample Output 2
201
Sample Input 3
3 2 100 100 100 80 120
Sample Output 3
100
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
以下の条件を満たす長さ N の整数列を辞書順で小さい方から順に全て出力して下さい。
- i 番目の要素は 1 以上 R_i 以下
- 総和が K の倍数
数列の辞書順とは？
数列 A = (A_1, \ldots, A_{|A|}) が B = (B_1, \ldots, B_{|B|}) より辞書順で真に小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。- |A|<|B| かつ (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}) である。
- ある整数 1\leq i\leq \min\{|A|,|B|\} が存在して、下記の 2 つがともに成り立つ。
- (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
- A_i < B_i
制約
- 入力は全て整数
- 1 \le N \le 8
- 2 \le K \le 10
- 1 \le R_i \le 5
入力
入力は以下の形式で標準入力から与えられる。
N K R_1 R_2 \dots R_N
出力
出力すべき数列が X 個あり、そのうち i 個目が A_i=(A_{i,1},A_{i,2},\dots,A_{i,N}) であったとき、答えを以下の形式で出力せよ。
A_{1,1} A_{1,2} \dots A_{1,N}
A_{2,1} A_{2,2} \dots A_{2,N}
\vdots
A_{X,1} A_{X,2} \dots A_{X,N}
入力例 1
3 2 2 1 3
出力例 1
1 1 2 2 1 1 2 1 3
出力すべき数列は 3 個で、辞書順で (1,1,2),(2,1,1),(2,1,3) です。
入力例 2
1 2 1
出力例 2
出力すべき数列が無い場合もあります。
この場合、出力は空で構いません。
入力例 3
5 5 2 3 2 3 2
出力例 3
1 1 1 1 1 1 2 2 3 2 1 3 1 3 2 1 3 2 2 2 1 3 2 3 1 2 1 2 3 2 2 2 1 3 2 2 2 2 2 2 2 2 2 3 1 2 3 1 2 2 2 3 1 3 1 2 3 2 1 2 2 3 2 2 1
Score : 300 points
Problem Statement
Print all integer sequences of length N that satisfy the following conditions, in ascending lexicographical order.
- The i-th element is between 1 and R_i, inclusive.
- The sum of all elements is a multiple of K.
What is lexicographical order for sequences?
A sequence A = (A_1, \ldots, A_{|A|}) is lexicographically smaller than B = (B_1, \ldots, B_{|B|}) if either 1. or 2. below holds:- |A|<|B| and (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}).
- There exists an integer 1\leq i\leq \min\{|A|,|B|\} such that both of the following are true:
- (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
- A_i < B_i
Constraints
- All input values are integers.
- 1 \le N \le 8
- 2 \le K \le 10
- 1 \le R_i \le 5
Input
The input is given from Standard Input in the following format:
N K R_1 R_2 \dots R_N
Output
Print the answer in the following format, where X is the number of sequences to print, the i-th of which is A_i=(A_{i,1},A_{i,2},\dots,A_{i,N}):
A_{1,1} A_{1,2} \dots A_{1,N}
A_{2,1} A_{2,2} \dots A_{2,N}
\vdots
A_{X,1} A_{X,2} \dots A_{X,N}
Sample Input 1
3 2 2 1 3
Sample Output 1
1 1 2 2 1 1 2 1 3
There are three sequences to be printed, which are (1,1,2),(2,1,1),(2,1,3) in lexicographical order.
Sample Input 2
1 2 1
Sample Output 2
There may be no sequences to print.
In this case, the output can be empty.
Sample Input 3
5 5 2 3 2 3 2
Sample Output 3
1 1 1 1 1 1 2 2 3 2 1 3 1 3 2 1 3 2 2 2 1 3 2 3 1 2 1 2 3 2 2 2 1 3 2 2 2 2 2 2 2 2 2 3 1 2 3 1 2 2 2 3 1 3 1 2 3 2 1 2 2 3 2 2 1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
N 頂点の木があり、頂点は 1, 2, \dots, N と番号付けられています。
i \, (1 \leq i \leq N - 1) 番目の辺は頂点 u_i と頂点 v_i を結び、重みは w_i です。
異なる頂点 u, v に対し、頂点 u から頂点 v までの最短パスに含まれる辺の重みの最大値を f(u, v) とおきます。
\displaystyle \sum_{i = 1}^{N - 1} \sum_{j = i + 1}^N f(i, j) を求めてください。
制約
- 2 \leq N \leq 10^5
- 1 \leq u_i, v_i \leq N
- 1 \leq w_i \leq 10^7
- 与えられるグラフは木である。
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
u_1 v_1 w_1
\vdots
u_{N - 1} v_{N - 1} w_{N - 1}
出力
答えを出力せよ。
入力例 1
3 1 2 10 2 3 20
出力例 1
50
f(1, 2) = 10, f(2, 3) = 20, f(1, 3) = 20 であるので、これらの和である 50 を出力します。
入力例 2
5 1 2 1 2 3 2 4 2 5 3 5 14
出力例 2
76
Score : 400 points
Problem Statement
We have a tree with N vertices numbered 1, 2, \dots, N.
The i-th edge (1 \leq i \leq N - 1) connects Vertex u_i and Vertex v_i and has a weight w_i.
For different vertices u and v, let f(u, v) be the greatest weight of an edge contained in the shortest path from Vertex u to Vertex v.
Find \displaystyle \sum_{i = 1}^{N - 1} \sum_{j = i + 1}^N f(i, j).
Constraints
- 2 \leq N \leq 10^5
- 1 \leq u_i, v_i \leq N
- 1 \leq w_i \leq 10^7
- The given graph is a tree.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
u_1 v_1 w_1
\vdots
u_{N - 1} v_{N - 1} w_{N - 1}
Output
Print the answer.
Sample Input 1
3 1 2 10 2 3 20
Sample Output 1
50
We have f(1, 2) = 10, f(2, 3) = 20, and f(1, 3) = 20, so we should print their sum, or 50.
Sample Input 2
5 1 2 1 2 3 2 4 2 5 3 5 14
Sample Output 2
76
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 475 点
問題文
2 次元平面上の N 個の点 (x_1,y_1),(x_2,y_2),\dots,(x_N,y_N) と、非負整数 D が与えられます。
整数の組 (x,y) であって、 \displaystyle \sum_{i=1}^N (|x-x_i|+|y-y_i|) \leq D を満たすものの個数を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq D \leq 10^6
- -10^6 \leq x_i, y_i \leq 10^6
- i\neq j ならば (x_i,y_i) \neq (x_j,y_j)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N D x_1 y_1 x_2 y_2 \vdots x_N y_N
出力
答えを出力せよ。
入力例 1
2 3 0 0 1 0
出力例 1
8
下図は、サンプル 1 の入力と答えを可視化したものです。青い点が入力を表します。青い点と赤い点の合計 8 点が、問題文中の条件を満たす点です。
入力例 2
2 0 0 0 2 0
出力例 2
0
入力例 3
6 100 9 -6 10 -1 2 10 -1 7 -7 5 -1 -4
出力例 3
419
Score : 475 points
Problem Statement
You are given N points (x_1, y_1), (x_2, y_2), \dots, (x_N, y_N) on a two-dimensional plane, and a non-negative integer D.
Find the number of integer pairs (x, y) such that \displaystyle \sum_{i=1}^N (|x-x_i|+|y-y_i|) \leq D.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq D \leq 10^6
- -10^6 \leq x_i, y_i \leq 10^6
- (x_i, y_i) \neq (x_j, y_j) for i \neq j.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N D x_1 y_1 x_2 y_2 \vdots x_N y_N
Output
Print the answer.
Sample Input 1
2 3 0 0 1 0
Sample Output 1
8
The following figure visualizes the input and the answer for Sample 1. The blue points represent the input. The blue and red points, eight in total, satisfy the condition in the statement.
Sample Input 2
2 0 0 0 2 0
Sample Output 2
0
Sample Input 3
6 100 9 -6 10 -1 2 10 -1 7 -7 5 -1 -4
Sample Output 3
419
Time Limit: 5 sec / Memory Limit: 1024 MiB
配点 : 550 点
問題文
H 行 W 列のマス目があり、最初、1 以上 (H\times W) 以下の整数がちょうど 1 つずつ書き込まれています。
具体的には、1\leq i\leq H, 1\leq j\leq W について、上から i 行目かつ左から j 列目のマスには S_{i,j} が書き込まれています。
以下、上から i 行目かつ左から j 列目のマスをマス (i,j) と呼びます。
次の操作を 高々 20 回 （0 回でも良い）繰り返すことで、
任意の整数の組 (i,j) (1\leq i\leq H, 1\leq j\leq W) について、
マス (i,j) に ((i-1)\times W+j) が書き込まれている状態にできるか判定し、
できる場合は必要な操作回数の最小値を出力してください。
20 回以下でできない場合（何回操作を繰り返してもできない場合を含む）は -1 を出力してください。
操作：マス目から (H-1) \times (W-1) の長方形を選んで 180 度回転させる。
より厳密には、整数 x,y (0 \leq x, y \leq 1) を選び、
1 \leq i \leq H-1, 1 \leq j \leq W-1 をみたすすべての整数の組 (i,j) について同時に、
マス (i+x,j+y) に書かれた整数をマス (H-i+x,W-j+y) に書かれた数に書き換える。
マス目に書き込まれている整数が条件をみたしていれば良く、書き込まれている向き等は考える必要がないことに注意してください。
制約
- 3\leq H,W\leq 8
- 1\leq S_{i,j}\leq H\times W
- (i,j)\neq (i',j') ならば S_{i,j}\neq S_{i',j'}
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
H W
S_{1,1} S_{1,2} \ldots S_{1,W}
S_{2,1} S_{2,2} \ldots S_{2,W}
\vdots
S_{H,1} S_{H,2} \ldots S_{H,W}
出力
問題文の条件をみたすために必要な操作回数の最小値を出力せよ。
ただし、20 回以下の操作で条件をみたすようにできないときは -1 を出力せよ。
入力例 1
3 3 9 4 3 2 1 8 7 6 5
出力例 1
2
次の順で操作を行うことで 2 回の操作で問題文の条件をみたすようにすることができます。
- 左上の長方形を選び、操作を行う。すなわち x=0, y=0 を選んで操作を行う。
- 右下の長方形を選び、操作を行う。すなわち x=1, y=1 を選んで操作を行う。
一方で 1 回以下の操作でみたすようにすることは不可能であるため、2 を出力します。
入力例 2
4 6 15 18 1 14 3 4 23 24 19 8 9 12 13 2 17 6 5 16 21 22 7 20 11 10
出力例 2
-1
20 回以下の操作で条件をみたすようにすることができないため、-1 を出力します。
入力例 3
4 6 1 4 13 16 15 18 21 20 9 12 23 10 17 14 5 6 3 2 11 22 7 24 19 8
出力例 3
20
入力例 4
4 3 1 2 3 4 5 6 7 8 9 10 11 12
出力例 4
0
Score: 550 points
Problem Statement
There is a grid with H rows and W columns. Initially, each integer from 1 to (H \times W) is written exactly once in the grid.
Specifically, for 1 \leq i \leq H and 1 \leq j \leq W, the cell at the i-th row from the top and the j-th column from the left contains S_{i,j}.
Below, let (i,j) denote the cell at the i-th row from the top and the j-th column from the left.
Determine if it is possible to reach a state where, for all pairs of integers (i,j) (1 \leq i \leq H, 1 \leq j \leq W),
the cell (i,j) contains the integer ((i-1) \times W + j) by repeating the following operation at most 20 times (possibly zero).
If it is possible, print the minimum number of operations required.
If it is impossible in 20 or fewer operations (including the case where it is impossible no matter how many times the operation is repeated), print -1.
Operation: Choose a rectangle of size (H-1) \times (W-1) from the grid and rotate it 180 degrees.
More precisely, choose integers x and y (0 \leq x, y \leq 1),
and for all pairs of integers (i,j) satisfying 1 \leq i \leq H-1 and 1 \leq j \leq W-1,
simultaneously replace the integer written in cell (i+x,j+y) with the number written in cell (H-i+x,W-j+y).
Note that it is only necessary for the integers written in the cells to satisfy the condition; the orientation in which they are written does not matter.
Constraints
- 3 \leq H,W \leq 8
- 1 \leq S_{i,j} \leq H \times W
- If (i,j) \neq (i',j'), then S_{i,j} \neq S_{i',j'}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
H W
S_{1,1} S_{1,2} \ldots S_{1,W}
S_{2,1} S_{2,2} \ldots S_{2,W}
\vdots
S_{H,1} S_{H,2} \ldots S_{H,W}
Output
Print the minimum number of operations required to meet the conditions of the problem statement.
If it is impossible to satisfy the conditions with 20 or fewer operations, output -1.
Sample Input 1
3 3 9 4 3 2 1 8 7 6 5
Sample Output 1
2
Operating in the following order will satisfy the conditions of the problem statement in 2 operations.
- Operate by choosing the rectangle in the top-left corner. That is, by choosing x=0 and y=0.
- Operate by choosing the rectangle in the bottom-right corner. That is, by choosing x=1 and y=1.
On the other hand, it is impossible to satisfy the conditions with one or fewer operations, so print 2.
Sample Input 2
4 6 15 18 1 14 3 4 23 24 19 8 9 12 13 2 17 6 5 16 21 22 7 20 11 10
Sample Output 2
-1
It is impossible to satisfy the conditions with 20 or fewer operations, so print -1.
Sample Input 3
4 6 1 4 13 16 15 18 21 20 9 12 23 10 17 14 5 6 3 2 11 22 7 24 19 8
Sample Output 3
20
Sample Input 4
4 3 1 2 3 4 5 6 7 8 9 10 11 12
Sample Output 4
0