まっすぐな道が 0 から L まであり、道ばたに街灯が n 本ある。 i 番目の街灯は位置 pᵢ にあり、今は pᵢ − rᵢ から pᵢ + rᵢ まで（両端を含む）を照らしている。 すべての街灯に同じ強さ t の増幅器をつけられる。 t は 0 以上の整数で、増幅器をつけるとすべての街灯が pᵢ − rᵢ − t から pᵢ + rᵢ + t までを照らす。 街灯は多くても k 本しかつけられない。 つけた街灯が照らす区間を合わせて、0 以上 L 以下のすべての点（整数でない点も含む）が照らされれば、道をすべて照らしたことになる。 二つの区間が端点一つだけで出会っても、その間にすき間はない。 道をすべて照らせる最も小さい t を出力せよ。
入力
一行目に n、L、k、続く n 行にそれぞれ pᵢ と rᵢ が空白区切りで与えられる。 1 ≤ n ≤ 10,000、0 ≤ L ≤ 1,000,000,000、1 ≤ k ≤ n、0 ≤ pᵢ ≤ L、0 ≤ rᵢ ≤ 1,000,000,000
出力
最も小さい t を一つ
例 1 · stdin
4 10 2
1 1
4 2
9 0
7 1
stdout
2
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
t を大きくするとすべての区間が広がるだけなので、t でできれば t + 1 でもできます。 だから答え t を二分探索します：lo = 0、hi = L（t = L なら道の上のどの街灯一本でも [0, L] をすべて照らせます）から始め、mid でできれば hi = mid、できなければ lo = mid + 1 と狭めれば lo が答えです。 一つの t でできるかは貪欲法で調べます：まだ照らしていない最も左の点 need（最初は 0）を照らせる街灯のうち、右端が最も遠いものをつけ、need をその端に移すことを k 回まで繰り返します。 すべての区間が同じ t だけ伸びるので、左端 p − r の順番は t によりません — 最初に一度だけ並べ替えておけば、調べるたびに前から一度なめるだけです（n log n + 31 × n）。 落とし穴その一：区間は閉区間なので、端が触れ合うだけでもつながります（左端 − t <= need）。 < と書くと [−1, 5] と [5, 11] がつながらないと見なして答えが大きくなります。 落とし穴その二：p + r は 20 億までなので 32 ビットの int（約 21 億）にぎりぎり入りますが、探索中に t を足すと 30 億まで行ってあふれます。 C・C++ は long long、Java・C# は long が必要で、Python の整数には上限がなく、JavaScript・TypeScript・Craykon の数は倍精度浮動小数点数なのでそのままで大丈夫です。 落とし穴その三：街灯を位置 p の順に並べると、半径が違うときに左端の順番と食い違い、前からなめる途中で左端がもっと小さい街灯を見落とします。 落とし穴その四：できる mid を hi = mid - 1 で捨てると答えを通り過ぎます — 答えの候補はいつも [lo, hi] の中に残します。 並べ替えは言語ごとに違います：Python はタプル (p - r, p + r) をそのまま sort()、JavaScript・TypeScript は sort((x, y) => x[0] - y[0])（比較関数がないと文字列として比べます）、Java Arrays.sort(lamps, (x, y) -> Long.compare(x[0], y[0]))、C# Array.Sort(lamps, (x, y) => x.left.CompareTo(y.left))、C++ は std::pair をそのまま std::sort、C の qsort は比較関数で x - y を int で返すとあふれることがあるので (x > y) - (x < y) を返します。 Craykon は lamps.並べ替え(左端順) のように負・0・正を返す関数を渡し、整数の割り算は 数学.商(lo + hi, 2) です。
Pythonmain.py · 40 行
import sysdata = sys.stdin.read().split()n, length, k = int(data[0]), int(data[1]), int(data[2])lamps = [] # (p - r, p + r): 늘이기 전에 비추는 구간for i in range(n): p, r = int(data[3 + 2 * i]), int(data[4 + 2 * i]) lamps.append((p - r, p + r))lamps.sort() # 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다def lamps_needed_ok(t): """모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가.""" need = 0 # 아직 비춘다고 확인하지 못한 가장 왼쪽 점 i = 0 best = -1 # 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 used = 0 while used < k: while i < n and lamps[i][0] - t <= need: # 끝이 닿기만 해도 이어진다(닫힌 구간) best = max(best, lamps[i][1] + t) i += 1 if best < need: # need를 비추는 등이 없다 return False used += 1 if best >= length: return True if best == need: # 더 나아갈 수 없다 return False need = best return Falselo, hi = 0, length # t = length이면 어느 등 하나로도 [0, length]를 다 비춘다while lo < hi: mid = (lo + hi) // 2 if lamps_needed_ok(mid): hi = mid else: lo = mid + 1print(lo)
JavaScriptmain.js · 34 行
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, length, k] = data;const lamps = []; // [p - r, p + r]: 늘이기 전에 비추는 구간for (let i = 0; i < n; i++) { const p = data[3 + 2 * i], r = data[4 + 2 * i]; lamps.push([p - r, p + r]);}lamps.sort((x, y) => x[0] - y[0]); // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다// 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가function canCover(t) { let need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점 let i = 0; let best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 for (let used = 1; used <= k; used++) { while (i < n && lamps[i][0] - t <= need) { // 끝이 닿기만 해도 이어진다(닫힌 구간) best = Math.max(best, lamps[i][1] + t); i++; } if (best < need) return false; // need를 비추는 등이 없다 if (best >= length) return true; if (best === need) return false; // 더 나아갈 수 없다 need = best; } return false;}let lo = 0, hi = length; // t = length이면 어느 등 하나로도 [0, length]를 다 비춘다while (lo < hi) { const mid = Math.floor((lo + hi) / 2); if (canCover(mid)) hi = mid; else lo = mid + 1;}console.log(lo);
TypeScriptmain.ts · 36 行
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, length, k] = data;const lamps: [left: number, right: number][] = []; // 늘이기 전에 비추는 구간 [p - r, p + r]for (let i = 0; i < n; i++) { const p = data[3 + 2 * i], r = data[4 + 2 * i]; lamps.push([p - r, p + r]);}lamps.sort((x, y) => x[0] - y[0]); // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다// 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가function canCover(t: number): boolean { let need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점 let i = 0; let best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 for (let used = 1; used <= k; used++) { while (i < n && lamps[i][0] - t <= need) { // 끝이 닿기만 해도 이어진다(닫힌 구간) best = Math.max(best, lamps[i][1] + t); i++; } if (best < need) return false; // need를 비추는 등이 없다 if (best >= length) return true; if (best === need) return false; // 더 나아갈 수 없다 need = best; } return false;}let lo = 0, hi = length; // t = length이면 어느 등 하나로도 [0, length]를 다 비춘다while (lo < hi) { const mid: number = Math.floor((lo + hi) / 2); if (canCover(mid)) hi = mid; else lo = mid + 1;}console.log(lo);
JavaMain.java · 54 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { static int n, k; static long length; static long[][] lamps; // {p - r, p + r}: 늘이기 전에 비추는 구간. p + r + t는 30억까지라 long // 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가 static boolean canCover(long t) { long need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점 int i = 0; long best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 for (int used = 1; used <= k; used++) { while (i < n && lamps[i][0] - t <= need) { // 끝이 닿기만 해도 이어진다(닫힌 구간) best = Math.max(best, lamps[i][1] + t); i++; } if (best < need) return false; // need를 비추는 등이 없다 if (best >= length) return true; if (best == need) return false; // 더 나아갈 수 없다 need = best; } return false; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); n = Integer.parseInt(st.nextToken()); length = Long.parseLong(st.nextToken()); k = Integer.parseInt(st.nextToken()); lamps = new long[n][]; for (int i = 0; i < n; i++) { st = new StringTokenizer(in.readLine()); long p = Long.parseLong(st.nextToken()); long r = Long.parseLong(st.nextToken()); lamps[i] = new long[] {p - r, p + r}; } // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다 Arrays.sort(lamps, (x, y) -> Long.compare(x[0], y[0])); long lo = 0, hi = length; // t = length이면 어느 등 하나로도 [0, length]를 다 비춘다 while (lo < hi) { long mid = (lo + hi) / 2; if (canCover(mid)) hi = mid; else lo = mid + 1; } System.out.println(lo); }}
C#Main.cs · 55 行
using System;class Program{ static int n, k; static long length; static (long left, long right)[] lamps; // 늘이기 전에 비추는 구간 [p - r, p + r]. p + r + t는 30억까지라 long // 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가 static bool CanCover(long t) { long need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점 int i = 0; long best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 for (int used = 1; used <= k; used++) { while (i < n && lamps[i].left - t <= need) // 끝이 닿기만 해도 이어진다(닫힌 구간) { best = Math.Max(best, lamps[i].right + t); i++; } if (best < need) return false; // need를 비추는 등이 없다 if (best >= length) return true; if (best == need) return false; // 더 나아갈 수 없다 need = best; } return false; } static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); n = int.Parse(first[0]); length = long.Parse(first[1]); k = int.Parse(first[2]); lamps = new (long left, long right)[n]; for (int i = 0; i < n; i++) { string[] w = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); long p = long.Parse(w[0]), r = long.Parse(w[1]); lamps[i] = (p - r, p + r); } // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다 Array.Sort(lamps, (x, y) => x.left.CompareTo(y.left)); long lo = 0, hi = length; // t = length이면 어느 등 하나로도 [0, length]를 다 비춘다 while (lo < hi) { long mid = (lo + hi) / 2; if (CanCover(mid)) hi = mid; else lo = mid + 1; } Console.WriteLine(lo); }}
C++main.cpp · 48 行
#include <algorithm>#include <iostream>#include <utility>#include <vector>int n, k;long long length;std::vector<std::pair<long long, long long>> lamps; // (p - r, p + r): 늘이기 전에 비추는 구간. p + r + t는 30억까지라 long long// 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가bool canCover(long long t) { long long need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점 int i = 0; long long best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 for (int used = 1; used <= k; used++) { while (i < n && lamps[i].first - t <= need) { // 끝이 닿기만 해도 이어진다(닫힌 구간) best = std::max(best, lamps[i].second + t); i++; } if (best < need) return false; // need를 비추는 등이 없다 if (best >= length) return true; if (best == need) return false; // 더 나아갈 수 없다 need = best; } return false;}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cin >> n >> length >> k; lamps.resize(n); for (auto& lamp : lamps) { long long p, r; std::cin >> p >> r; lamp = {p - r, p + r}; } std::sort(lamps.begin(), lamps.end()); // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다 long long lo = 0, hi = length; // t = length이면 어느 등 하나로도 [0, length]를 다 비춘다 while (lo < hi) { long long mid = (lo + hi) / 2; if (canCover(mid)) hi = mid; else lo = mid + 1; } std::cout << lo << '\n'; return 0;}
Cmain.c · 55 行
#include <stdio.h>#include <stdlib.h>#define MAXN 10000typedef struct { long long left, right; /* 늘이기 전에 비추는 구간 [p - r, p + r]. p + r + t는 30억까지라 long long */} Lamp;static Lamp lamps[MAXN];static int n, k;static long long length;static int byLeft(const void* a, const void* b) { long long x = ((const Lamp*)a)->left, y = ((const Lamp*)b)->left; return (x > y) - (x < y); /* x - y를 int로 돌려주면 넘칠 수 있다 */}/* 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있으면 1 */static int canCover(long long t) { long long need = 0; /* 아직 비춘다고 확인하지 못한 가장 왼쪽 점 */ long long best = -1; /* 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 */ int i = 0; for (int used = 1; used <= k; used++) { while (i < n && lamps[i].left - t <= need) { /* 끝이 닿기만 해도 이어진다(닫힌 구간) */ if (lamps[i].right + t > best) best = lamps[i].right + t; i++; } if (best < need) return 0; /* need를 비추는 등이 없다 */ if (best >= length) return 1; if (best == need) return 0; /* 더 나아갈 수 없다 */ need = best; } return 0;}int main(void) { if (scanf("%d %lld %d", &n, &length, &k) != 3) return 0; for (int i = 0; i < n; i++) { long long p, r; scanf("%lld %lld", &p, &r); lamps[i].left = p - r; lamps[i].right = p + r; } qsort(lamps, n, sizeof lamps[0], byLeft); /* 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다 */ long long lo = 0, hi = length; /* t = length이면 어느 등 하나로도 [0, length]를 다 비춘다 */ while (lo < hi) { long long mid = (lo + hi) / 2; if (canCover(mid)) hi = mid; else lo = mid + 1; } printf("%lld\n", lo); return 0;}
Craykonmain.cray · 62 行
// 모든 등을 t만큼 늘였을 때 k개 이하로 [0, 길이]를 다 비출 수 있는가비출수있나(lamps, 길이, k, t){ need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점 i = 0; best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 繰り返す (used = 1; used <= k; used++) { 間 (i < lamps.個数 && lamps[i][0] - t <= need) { best = 数学.大きい方(best, lamps[i][1] + t); i++; } もし (best < need) { 返す 偽; } もし (best >= 길이) { 返す 真; } もし (best == need) { 返す 偽; } need = best; } 返す 偽;}왼쪽끝순(앞, 뒤){ 返す 앞[0] - 뒤[0];}첫줄 = コンソール.数読み();n = 첫줄[0];길이 = 첫줄[1];k = 첫줄[2];lamps = []; // [p - r, p + r]: 늘이기 전에 비추는 구간繰り返す (j = 0; j < n; j++){ 등 = コンソール.数読み(); lamps.追加([등[0] - 등[1], 등[0] + 등[1]]);}lamps.並べ替え(왼쪽끝순); // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다lo = 0;hi = 길이; // t = 길이이면 어느 등 하나로도 [0, 길이]를 다 비춘다間 (lo < hi){ mid = 数学.商(lo + hi, 2); もし (비출수있나(lamps, 길이, k, mid)) { hi = mid; } でなければ { lo = mid + 1; }}コンソール.書く(lo);