長さ a₁, …, aₙ のリボンが n 本ある。
すべての切れ端が同じ正の整数の長さ L になるようにリボンを切って、切れ端を k 本以上作りたい。
リボンをつなぐことはできず、切った残りは捨てる（長さ a のリボンからは a を L で割った商の本数だけ切れ端がとれる）。
作れる最大の L を出力せよ。
L = 1 でも k 本作れなければ 0 を出力する。
3 4 5 5 5
2
2 7 3 3
0
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
L を 1 から一つずつ増やすと 20 億回までかかります。
L が大きいほど切れ端は減るので「k 本以上か」は前が真、後ろが偽になり、二分探索なら 31 回で見つかります。
条件を関数で受け取る探索関数を分けておけば、ほかの問題にもそのまま使えます：Python は関数名をそのまま渡し、JavaScript・TypeScript はアロー関数 (x: number) => boolean、Java IntPredicate と ok.test(mid)、C# Func<int, bool>、C++ std::function<bool(int)> とラムダ、C は関数ポインタ int (*ok)(int)、Craykon は関数名を値として渡して ok(mid) で呼びます。
罠はあふれです。
① 真ん中 (lo + hi) / 2：長さが int（約 21 億）に収まっても lo + hi は 40 億になり、Java・C#・C・C++ であふれます — lo + (hi - lo) / 2 と書きます。
JavaScript の (lo + hi) >> 1 も 32 ビット整数に変えるので同じく壊れます（Math.floor を使います）。
Python・Craykon はあふれません。
② 切れ端の数は 2×10¹³ まで増えるので long/long long が必要です。
最後に、L = 1 でも足りなければ答えは 1 ではなく 0 です。
def last_true(lo, hi, ok): """lo..hi 에서 ok(x)가 참인 가장 큰 x. ok는 앞쪽이 참, 뒤쪽이 거짓이어야 한다. 없으면 lo - 1.""" answer = lo - 1 while lo <= hi: mid = (lo + hi) // 2 if ok(mid): answer = mid lo = mid + 1 else: hi = mid - 1 return answer n, k = map(int, input().split())a = list(map(int, input().split())) def enough(length): return sum(x // length for x in a) >= k print(last_true(1, max(a), enough))// lo..hi 에서 ok(x)가 참인 가장 큰 x. ok는 앞쪽이 참, 뒤쪽이 거짓이어야 한다. 없으면 lo - 1.function lastTrue(lo, hi, ok) { let answer = lo - 1; while (lo <= hi) { const mid = Math.floor((lo + hi) / 2); if (ok(mid)) { answer = mid; lo = mid + 1; } else { hi = mid - 1; } } return answer;} const [n, k, ...a] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const enough = (length) => a.reduce((sum, x) => sum + Math.floor(x / length), 0) >= k;console.log(lastTrue(1, Math.max(...a), enough));import { readFileSync } from "node:fs"; // lo..hi 에서 ok(x)가 참인 가장 큰 x. ok는 앞쪽이 참, 뒤쪽이 거짓이어야 한다. 없으면 lo - 1.function lastTrue(lo: number, hi: number, ok: (x: number) => boolean): number { let answer = lo - 1; while (lo <= hi) { const mid = Math.floor((lo + hi) / 2); if (ok(mid)) { answer = mid; lo = mid + 1; } else { hi = mid - 1; } } return answer;} const [n, k, ...a]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const enough = (length: number): boolean => a.reduce((sum, x) => sum + Math.floor(x / length), 0) >= k;console.log(lastTrue(1, Math.max(...a), enough));import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;import java.util.function.IntPredicate; public class Main { // lo..hi 에서 ok(x)가 참인 가장 큰 x. 없으면 lo - 1. static int lastTrue(int lo, int hi, IntPredicate ok) { int answer = lo - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // (lo + hi) / 2 는 int를 넘칠 수 있다 if (ok.test(mid)) { answer = mid; lo = mid + 1; } else { hi = mid - 1; } } return answer; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); long k = Long.parseLong(st.nextToken()); int[] a = new int[n]; int longest = 0; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) { a[i] = Integer.parseInt(st.nextToken()); longest = Math.max(longest, a[i]); } IntPredicate enough = length -> { long pieces = 0; for (int x : a) pieces += x / length; return pieces >= k; }; System.out.println(lastTrue(1, longest, enough)); }}using System;using System.Linq; class Program{ // lo..hi 에서 ok(x)가 참인 가장 큰 x. 없으면 lo - 1. static int LastTrue(int lo, int hi, Func<int, bool> ok) { int answer = lo - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // (lo + hi) / 2 는 int를 넘칠 수 있다 if (ok(mid)) { answer = mid; lo = mid + 1; } else { hi = mid - 1; } } return answer; } static void Main() { long k = long.Parse(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries)[1]); int[] a = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); Func<int, bool> enough = length => a.Sum(x => (long)(x / length)) >= k; Console.WriteLine(LastTrue(1, a.Max(), enough)); }}#include <algorithm>#include <functional>#include <iostream>#include <vector> // lo..hi 에서 ok(x)가 참인 가장 큰 x. 없으면 lo - 1.int lastTrue(int lo, int hi, const std::function<bool(int)>& ok) { int answer = lo - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // (lo + hi) / 2 는 int를 넘칠 수 있다 if (ok(mid)) { answer = mid; lo = mid + 1; } else { hi = mid - 1; } } return answer;} int main() { int n; long long k; std::cin >> n >> k; std::vector<int> a(n); for (int& x : a) std::cin >> x; auto enough = [&](int length) { long long pieces = 0; for (int x : a) pieces += x / length; return pieces >= k; }; std::cout << lastTrue(1, *std::max_element(a.begin(), a.end()), enough) << "\n";}#include <stdio.h> static int n;static long long k;static int a[10000]; /* lo..hi 에서 ok(x)가 참인 가장 큰 x. 없으면 lo - 1. ok는 함수 포인터로 받는다. */static int last_true(int lo, int hi, int (*ok)(int)) { int answer = lo - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; /* (lo + hi) / 2 는 int를 넘칠 수 있다 */ if (ok(mid)) { answer = mid; lo = mid + 1; } else { hi = mid - 1; } } return answer;} static int enough(int length) { long long pieces = 0; for (int i = 0; i < n; i++) pieces += a[i] / length; return pieces >= k;} int main(void) { int longest = 0; scanf("%d %lld", &n, &k); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); if (a[i] > longest) longest = a[i]; } printf("%d\n", last_true(1, longest, enough)); return 0;}// lo..hi 에서 ok(x)가 참인 가장 큰 x. ok는 앞쪽이 참, 뒤쪽이 거짓이어야 한다. 없으면 lo - 1.가장큰참(lo, hi, ok){ answer = lo - 1; 間 (lo <= hi) { mid = 数学.商(lo + hi, 2); もし (ok(mid)) { answer = mid; lo = mid + 1; } でなければ { hi = mid - 1; } } 返す answer;} // 길이 length로 자르면 k조각 이상 나오나충분한가(length){ pieces = 0; それぞれ (x の中 a) { pieces += 数学.商(x, length); } 返す pieces >= k;} 첫줄 = コンソール.数読み();k = 첫줄[1];a = コンソール.数読み();longest = 0;それぞれ (x の中 a){ longest = 数学.大きい方(longest, x);}コンソール.書く(가장큰참(1, longest, 충분한가));