/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
高橋君は、ある直線状の道路に沿って K 個の避難所を設置する計画を立てています。道路は数直線として表され、 N 個の集落が数直線上の相異なる整数座標 X_1, X_2, \ldots, X_N にそれぞれ位置しています。
高橋君は、ちょうど K 個の避難所をこの数直線上に設置します。避難所は整数座標に限らず任意の実数座標に設置でき、集落と同じ座標にも設置できます。ただし、異なる 2 つの避難所を同じ座標に設置することはできません。
各集落の住民は、自分の集落から最も近い避難所へ避難します。最も近い避難所が複数ある場合は、そのうち座標が最も小さいものへ避難するものとします。
ある避難所の 受入数 とは、その避難所を避難先とする集落の個数として定義されます。高橋君は、すべての避難所の受入数が 1 以上となるように避難所を配置しなければなりません。すなわち、どの避難所にも少なくとも 1 つの集落が避難先として割り当てられている必要があります。これは、避難所を無駄な位置に配置して実質的に使わないことを防ぐための条件です。K \leq N であるため、この条件を満たす配置は必ず存在します。
この条件を満たす避難所の配置のうち、各集落からその避難先の避難所までの距離の最大値 を最小化したいです。この最大値の最小値を d とします。
d は 0 以上であり、整数または半整数（整数に \frac{1}{2} を加えた値）のいずれかになることが証明できます。したがって 2d は必ず非負整数となります。2d の値を整数として出力してください。
制約
- 1 \leq K \leq N \leq 2 \times 10^5
- 0 \leq X_1 < X_2 < \cdots < X_N \leq 10^9
- 入力はすべて整数である
入力
N K X_1 X_2 \ldots X_N
- 1 行目には、集落の数を表す整数 N と、設置する避難所の数を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各集落の座標を表す整数 X_1, X_2, \ldots, X_N が、スペース区切りで与えられる。
出力
すべての避難所の受入数が 1 以上となる配置のうち、各集落からその避難先の避難所までの距離の最大値として達成可能な最小値を d とする。2d の値を整数として 1 行で出力せよ。
入力例 1
5 2 0 2 3 10 12
出力例 1
3
入力例 2
4 4 1 5 9 20
出力例 2
0
入力例 3
12 4 0 3 4 8 15 16 23 42 43 44 60 75
出力例 3
15
入力例 4
30 7 0 1 2 10 11 20 35 36 37 50 51 52 80 100 101 150 151 152 153 200 260 261 300 301 302 400 500 700 701 900
出力例 4
100
入力例 5
1 1 1000000000
出力例 5
0
Score : 400 pts
Problem Statement
Takahashi is planning to place K shelters along a straight road. The road is represented as a number line, and N villages are located at distinct integer coordinates X_1, X_2, \ldots, X_N on the number line.
Takahashi will place exactly K shelters on this number line. Shelters can be placed at any real-valued coordinate, not limited to integers, and can be placed at the same coordinate as a village. However, two different shelters cannot be placed at the same coordinate.
The residents of each village will evacuate to the nearest shelter from their village. If there are multiple nearest shelters, they will evacuate to the one with the smallest coordinate.
The acceptance count of a shelter is defined as the number of villages assigned to that shelter as their evacuation destination. Takahashi must place the shelters such that the acceptance count of every shelter is at least 1. In other words, every shelter must have at least one village assigned to it as an evacuation destination. This condition prevents placing shelters at wasteful positions where they are effectively unused. Since K \leq N, a placement satisfying this condition always exists.
Among all shelter placements satisfying this condition, we want to minimize the maximum distance from each village to its assigned shelter. Let d be the minimum value of this maximum distance.
It can be proven that d is non-negative and is either an integer or a half-integer (an integer plus \frac{1}{2}). Therefore, 2d is always a non-negative integer. Output the value of 2d as an integer.
Constraints
- 1 \leq K \leq N \leq 2 \times 10^5
- 0 \leq X_1 < X_2 < \cdots < X_N \leq 10^9
- All inputs are integers
Input
N K X_1 X_2 \ldots X_N
- The first line contains an integer N representing the number of villages and an integer K representing the number of shelters to place, separated by a space.
- The second line contains integers X_1, X_2, \ldots, X_N representing the coordinates of each village, separated by spaces.
Output
Among all placements where every shelter has an acceptance count of at least 1, let d be the minimum achievable value of the maximum distance from each village to its assigned shelter. Output the value of 2d as an integer on a single line.
Sample Input 1
5 2 0 2 3 10 12
Sample Output 1
3
Sample Input 2
4 4 1 5 9 20
Sample Output 2
0
Sample Input 3
12 4 0 3 4 8 15 16 23 42 43 44 60 75
Sample Output 3
15
Sample Input 4
30 7 0 1 2 10 11 20 35 36 37 50 51 52 80 100 101 150 151 152 153 200 260 261 300 301 302 400 500 700 701 900
Sample Output 4
100
Sample Input 5
1 1 1000000000
Sample Output 5
0