Бинпоиск по ответу: когда применять и как выбирать инвариант ТЕМА

О чём статья

Бинпоиск по ответу — техника, после освоения которой десятки задач полосы 1400–1900 становятся понятными по одной схеме. Идея в одно предложение: вместо того чтобы конструировать ответ, мы угадываем его половинным делением, и на каждом шаге задаём про кандидата только один вопрос — «достижим или нет?».

Эта статья — не разбор конкретной задачи. Цель — показать, по каким сигналам в условии узнавать технику, как формулировать инвариант проверки, чем различаются две формы шаблона («ищу максимум, при котором проверка ещё проходит» и «ищу минимум, при котором проверка уже проходит»), и какие ловушки границ съедают часы отладки даже у тех, кто уверенно пишет обычный бинпоиск по массиву. Базовый шаблон разбирается на двух задачах нарастающей сложности; глубже техника раскрывается в отдельных разборах серии.

---

Когда применять: сигналы в условии

Бинпоиск по ответу уместен, когда ответ — это число (часто целое, иногда вещественное), и про него можно сказать предикат «такое значение достижимо», который меняет значение ровно один раз при движении по диапазону кандидатов. Узнаваемые маркеры:

• «Найти максимальный $x$, при котором …» или «найти минимальный $x$, при котором …». Слово «максимальный/минимальный» — прямой сигнал к перебору ответа, а формат «при котором» обычно прячет внутри проверку.
• «Минимизировать максимум» или «максимизировать минимум». Классическая структура: ответ — это значение функции, аргумент которой — план действий, и план оптимизируется по min/max от чего-то локального. Почти всегда сводится к «зафиксируй $x$ → проверь, существует ли план, в котором локальный максимум $\le x$ (или локальный минимум $\ge x$)».
• Прямая конструкция «плохо параметризуется». Условие даёт сложную систему ограничений; перебрать все планы — экспонента; но «зафиксировать ответ и проверить план» — линейное или почти линейное.
• Большой диапазон ответа, но дешёвый предикат. Ответ может быть до $10^{18}$, а проверка работает за $O(n)$ или $O(n \log n)$ — тогда $\log$ от диапазона помещается в TL, а $n \cdot$ диапазон — нет.
• «За какое минимальное время / минимальное число шагов / минимальный ресурс …» — частный случай. Время/шаги/ресурс — кандидат, бинпоиск по нему.

Если вместо отдельных сигналов в условии видно сразу «минимизируй максимум» или «максимизируй минимум» — стоит начать решение с бинпоиска по ответу, даже если первая мысль была про DP или жадный. Часто эта формулировка превращает «сложную задачу про план» в «простую задачу про проверку».

---

Базовый шаблон

Идея в одну фразу

Завести диапазон кандидатов $[\textit{lo}, \textit{hi}]$ для ответа и функцию-предикат can(x). Сужать диапазон половинным делением, опираясь на единственное свойство — монотонность предиката: внутри диапазона есть ровно одна точка перехода false → true (или true → false).

Два варианта формы

Бинпоиск по ответу почти всегда сводится к одной из двух форм:

(A) «Ищу максимальный $x$, при котором can(x) = true». Предикат истинен на префиксе и ложен на суффиксе. Ответ — правая граница истинного префикса.

(B) «Ищу минимальный $x$, при котором can(x) = true». Предикат ложен на префиксе и истинен на суффиксе. Ответ — левая граница истинного суффикса.

Это не разные техники, а одна и та же — но с разными ответами на одинаковые mid. Распознавать форму важно потому, что от неё зависит направление сдвига границ и способ вычисления mid: иначе шаблон зациклится на $\textit{lo} + 1 = \textit{hi}$.

Псевдокод формы (A) — максимум среди удовлетворяющих

lo ← минимально возможный ответ
hi ← максимально возможный ответ
пока lo < hi:
    mid ← (lo + hi + 1) / 2          // округление вверх — важно для (A)
    если can(mid):
        lo ← mid                      // mid сам кандидат, граница включает его
    иначе:
        hi ← mid - 1                  // mid не подходит, отбрасываем
вернуть lo  // = hi

Псевдокод формы (B) — минимум среди удовлетворяющих

lo ← минимально возможный ответ
hi ← максимально возможный ответ
пока lo < hi:
    mid ← (lo + hi) / 2              // округление вниз — важно для (B)
    если can(mid):
        hi ← mid                      // mid сам кандидат, граница включает его
    иначе:
        lo ← mid + 1                  // mid не подходит, отбрасываем
вернуть lo  // = hi

Почему именно так округляется mid

Когда $\textit{lo}$ и $\textit{hi}$ соседние ($\textit{hi} = \textit{lo} + 1$), цикл должен завершиться за один шаг. В форме (A) (lo + hi) / 2 с округлением вниз даёт $\textit{lo}$, и при can(lo) = true строка lo = mid оставляет $\textit{lo}$ на месте — бесконечный цикл. Округление вверх даёт $\textit{hi}$: при can(hi) = true сразу $\textit{lo} = \textit{hi}$, и цикл закрывается. Зеркально в форме (B): округление вверх ловит зацикливание, нужно округлять вниз.

Это самая частая ошибка новичка с бинпоиском по ответу. Лекарство — не пытаться вспоминать формулы, а держать в голове картину «соседние границы за один шаг»: для каждой формы проверить в уме, как ведёт себя цикл на $\textit{hi} = \textit{lo} + 1$.

Сложность шаблона

$O(\textit{can}(n) \cdot \log (\textit{hi} - \textit{lo}))$, где $\textit{can}(n)$ — сложность одной проверки. Для типичных задач: $\textit{can} = O(n)$, $\log$ диапазона $\le 60$ (даже при ответе до $10^{18}$). Итого $\sim 10^7$ операций при $n = 10^5$ — комфортно в любой TL.

Что делать с вещественным ответом

Если ответ — вещественное число (геометрия, оптимизация плотности), форма та же, но условие выхода — не $\textit{lo} < \textit{hi}$, а фиксированное число итераций (типично 60–100 — этого хватит на 14–18 значащих цифр) или ширина $\textit{hi} - \textit{lo} < \varepsilon$. В этой статье вещественный случай не разбираем — обе задачи-иллюстрации целочисленные.

---

Как выбирать инвариант проверки

Это самая содержательная часть техники. «Написать бинпоиск» — лёгкая часть; «понять, что именно проверять» — основная работа. Несколько практических наводок.

Первый шаг: переформулировать вопрос как «можно ли … при …». Исходный вопрос — «найти максимальное $L$, чтобы получить $\ge k$ кусков». Переформулирован — «при фиксированном $L$, можно ли получить $\ge k$ кусков?». Второй вопрос — это и есть can(L). Если переформулировка вызывает затруднение — техника, скорее всего, не подойдёт.

Второй шаг: проверить монотонность. Если ответ на «достижим ли $x$» меняется при увеличении $x$ ровно один раз — техника работает. Если меняется несколько раз (есть «плохие» $x$ внутри хороших) — это не бинпоиск по ответу, а что-то другое (часто DP или прямая конструкция). Доказательство монотонности на ревью занимает 1–2 строки; если оно не пишется — повод задуматься, точно ли это та техника.

Третий шаг: выбрать форму (A) или (B). Если максимизируем — (A); если минимизируем — (B). Это банально, но в условиях вида «минимизируй максимум» легко сбиться: мы минимизируем максимум, поэтому форма (B), а не (A); кандидат $x$ — значение максимума, а проверка — «существует ли план, в котором максимум $\le x$».

Четвёртый шаг: выбрать границы $\textit{lo}$ и $\textit{hi}$. Простой принцип: $\textit{lo}$ — гарантированно недостижимый снизу ответ (или граница, при которой can тривиально истинна); $\textit{hi}$ — гарантированно достижимый сверху. Чем плотнее границы — тем меньше итераций (хотя log всё равно даст лимит). Иногда полезно сразу установить $\textit{lo} = \max(a_i)$ или подобную «физическую» нижнюю границу, чтобы избежать вырожденных случаев в can.

---

Задача-иллюстрация 1: распил досок (~CF 1400)

Условие

Есть $n$ деревянных досок целочисленной длины $a_1, \ldots, a_n$. Нужно нарезать из них не менее $k$ кусков одинаковой целочисленной длины $L$. Каждая доска нарезается независимо: из доски длины $a_i$ получится ровно $\lfloor a_i / L \rfloor$ кусков длины $L$, остаток (если есть) выбрасывается. Найти максимальное значение $L$, при котором суммарно можно получить $\ge k$ кусков. Если суммарно длин всех досок меньше $k$, ответом считается $0$.

Ограничения. $1 \le n \le 10^5$, $1 \le k \le 2 \cdot 10^9$, $1 \le a_i \le 10^9$.

Формат ввода. В первой строке — $n$ и $k$. Во второй строке — $n$ целых чисел $a_1, \ldots, a_n$.

Формат вывода. Одно целое число — максимальное $L$.

Пример. $n = 4$, $k = 11$, $a = [802, 743, 457, 539]$.

При $L = 200$: $\lfloor 802/200 \rfloor + \lfloor 743/200 \rfloor + \lfloor 457/200 \rfloor + \lfloor 539/200 \rfloor = 4 + 3 + 2 + 2 = 11$ — ровно $k$. При $L = 201$: $3 + 3 + 2 + 2 = 10 < k$ — недостижимо. Значит, ответ — 200.

Выбор инварианта

Переформулировка: «при фиксированном $L$, верно ли $\sum_{i=1}^{n} \lfloor a_i / L \rfloor \ge k$?». Это и есть can(L).

Монотонность: при $L_1 < L_2$ для каждой доски $\lfloor a_i / L_1 \rfloor \ge \lfloor a_i / L_2 \rfloor$ (с увеличением длины куска число кусков из той же доски не растёт). Значит, сумма по $i$ тоже не растёт; точка перехода «истина → ложь» единственная. Форма — (A), ищем максимальное $L$ с can(L) = true.

Границы: $\textit{lo} = 1$ (при $L = 1$ кусков ровно $\sum a_i$ — если этого мало, отвечаем $0$ отдельной проверкой). $\textit{hi} = \max a_i$ (при $L > \max a_i$ из каждой доски получится 0 кусков, проверка тривиально ложна — нет смысла перебирать).

Применение шаблона

lo, hi ← 1, max(a)
если sum(a) < k:
    вернуть 0
пока lo < hi:
    mid ← (lo + hi + 1) / 2
    cnt ← sum(a[i] / mid для всех i)
    если cnt ≥ k:
        lo ← mid
    иначе:
        hi ← mid - 1
вернуть lo

Сложность: $O(n \log(\max a))$, в нашем примере $\sim 10^5 \cdot 30 = 3 \cdot 10^6$ операций.

Проверка на примере

$lo = 1$, $hi = 802$. Сумма $a$ = 2541 $\ge 11$, не вырожденный случай.

Итог: $lo = hi = 200$. ✓

Код решения

Что поменялось по сравнению с базовым шаблоном

• Конкретный предикат. Шаблонное can(mid) стало одной строкой — суммой $\lfloor a_i / \textit{mid} \rfloor$. Линейный проход, никаких структур.
• Ранний выход. Цикл подсчёта прерывается, как только сумма достигла $k$ — это не меняет асимптотику, но даёт постоянный фактор: «лёгкие» кандидаты проверяются быстрее.
• Вырожденный случай. Отдельная проверка $\sum a_i < k$ — без неё шаблон возвращал бы $1$, что неверно (нельзя нарезать $k$ кусков из недостаточной суммарной длины).
• Тип данных в C++. $k$ до $2 \cdot 10^9$ не помещается в int. Сумма $a_i$ — до $10^{14}$. Везде нужен long long. В Python типы автоматически произвольной точности.
• mid в C++. Запись lo + (hi - lo + 1) / 2 — защита от переполнения lo + hi, если границы близки к LLONG_MAX. В этой задаче не критично, но привычка полезная.

---

Задача-иллюстрация 2: минимаксная разрезка массива (~CF 1700)

Условие

Дан массив $a$ из $n$ положительных целых чисел и целое $k$ ($1 \le k \le n$). Нужно разделить массив на ровно $k$ непустых непрерывных подмассивов так, чтобы максимум сумм этих подмассивов был минимален. Вывести этот минимум.

Ограничения. $1 \le n \le 10^5$, $1 \le k \le n$, $1 \le a_i \le 10^9$.

Формат ввода. В первой строке — $n$ и $k$. Во второй строке — $a_1, \ldots, a_n$.

Формат вывода. Одно целое число — минимальное возможное значение максимальной суммы среди $k$ подмассивов.

Пример. $n = 5$, $k = 2$, $a = [7, 2, 5, 10, 8]$.

Варианты деления на 2 подмассива:

Минимум — 18.

Выбор инварианта

Прямой перебор разбиений — экспонента ($\binom{n-1}{k-1}$). DP даёт $O(n^2 k)$, что на $n = 10^5$ не помещается. Бинпоиск по ответу даёт $O(n \log(\sum a))$.

Переформулировка: «при фиксированном $x$, можно ли разрезать массив на не более $k$ подмассивов так, чтобы каждая сумма $\le x$?». Это и есть can(x).

Заметим важную деталь: исходный вопрос — про ровно $k$ подмассивов, а проверка — про не более $k$. Почему это эквивалентно? Если получилось разрезать на $k' < k$ подмассивов с суммой каждого $\le x$, то любой подмассив можно дополнительно разрезать (отщепить от конца один элемент в новый подмассив — это не увеличит ни одну сумму). Значит, при $k' \le k$ деление на ровно $k$ подмассивов с тем же ограничением тоже существует. Поэтому проверка «$\le k$» эквивалентна «$= k$ при возможности дополнительно дробить».

Монотонность: при увеличении $x$ нужно столько же или меньше подмассивов (порог стал свободнее, любой работающий план для меньшего $x$ работает и для большего). Точка перехода — единственная. Форма — (B), ищем минимальное $x$ с can(x) = true.

Границы: $\textit{lo} = \max a_i$ — снизу не имеет смысла идти, потому что один элемент уже занимает подмассив, и его сумма не может быть меньше его значения. $\textit{hi} = \sum a_i$ — сверху достаточно одного подмассива.

Жадная проверка

can(x): жадно набираем подмассив, пока сумма $\le x$; как только следующий элемент переполняет — закрываем подмассив и начинаем новый. В конце сравниваем число подмассивов с $k$.

groups ← 1
cur    ← 0
для v из a:
    если cur + v ≤ x:
        cur ← cur + v
    иначе:
        groups ← groups + 1
        cur    ← v
вернуть (groups ≤ k)

Почему жадно — оптимально? Допустим, есть решение с $g$ подмассивами, в котором первый подмассив короче, чем жадный. Заберём один элемент из второго подмассива и приклеим к первому — сумма первого не превысит $x$ (мы могли это сделать жадно — значит, помещается); сумма второго стала меньше — тоже $\le x$. После цепочки таких обменов получим жадное деление с тем же числом подмассивов. Значит, жадное — оптимально по числу подмассивов при фиксированном пороге $x$.

Сложность одной проверки: $O(n)$.

Применение шаблона

lo, hi ← max(a), sum(a)
пока lo < hi:
    mid ← (lo + hi) / 2
    если can(mid):
        hi ← mid
    иначе:
        lo ← mid + 1
вернуть lo

Сложность: $O(n \log (\sum a))$. На $n = 10^5$, $\sum a$ до $10^{14}$ — порядка $5 \cdot 10^6$ операций.

Проверка на примере

$a = [7, 2, 5, 10, 8]$, $k = 2$. $\textit{lo} = \max a = 10$, $\textit{hi} = \sum a = 32$.

Подробнее шаг 4: $cur = 0$, добавляем 7 → 7; +2 → 9; +5 → 14; +10 → 24; +8 → 32 > 26, закрываем, новый = 8. Итог: подмассивы $[7,2,5,10]$ и $[8]$? Нет, проверим внимательнее. После 14 ($cur = 14$) пробуем добавить 10: $14 + 10 = 24 \le 26$, добавляем, $cur = 24$. Пробуем добавить 8: $24 + 8 = 32 > 26$ — закрываем подмассив, $groups = 2$, $cur = 8$. В конце $groups = 2 \le k = 2$ — да. Значит, я выше посчитал неправильно; пересчитаем шаги.

Перепроверим жадное деление руками:

$x = 21$: $cur = 0$; $+7=7$; $+2=9$; $+5=14$; $+10=24>21$ → новая, $cur = 10$; $+8=18 \le 21$, $cur = 18$. Итог 2 группы? Нет, в момент превышения мы увеличиваем groups с 1 до 2. После прохода $groups = 2$. $2 \le k = 2$ — да. Значит, $x = 21$ достижимо, $hi = 21$. (Я ошибся в первом проходе таблицы — на 21 уже всё помещается.)

Пересоставим таблицу аккуратно:

Итог: $lo = hi = 18$. ✓ Совпадает с прямым перебором.

Код решения

Что поменялось по сравнению с базовым шаблоном

• Предикат не очевиден. В первой задаче can напрашивалась сразу из условия. Здесь её пришлось вывести через переформулировку «не более $k$» вместо «ровно $k$» и доказать эквивалентность дроблением подмассивов. Это типичный шаг в задачах на минимакс.
• Жадная проверка требует обоснования. Простой жадный перебор «работает, потому что очевидно» — частая ошибка. На этой задаче — короткое доказательство exchange argument, всего пара строк, но без него не написать can уверенно.
• Нижняя граница не нулевая. $\textit{lo} = \max a$ — следствие физики задачи: ни один план не даст максимум меньше единственного элемента. Без этой нижней границы шаблон работал бы корректно, но лишние итерации съели бы лимит на больших данных.
• Ранний выход в can. Как только $groups > k$, возвращаем false — это даёт постоянный фактор, особенно для маленьких $x$.
• long long обязательно. Сумма до $10^{14}$, $mid$ — комбинация $lo$ и $hi$. В C++ — long long везде. В Python — типы автоматические.

---

Типичные ошибки

Не «ошибки в конкретной задаче», а именно ошибки в применении техники — те, что повторяются от задачи к задаче.

1. Зацикливание из-за неправильного округления mid. Запись mid = (lo + hi) / 2 с округлением вниз в форме (A) — классическая ловушка: при $\textit{hi} = \textit{lo} + 1$ и can(lo) = true граница не сдвигается. Лекарство — не пытаться запоминать формулы, а проверять цикл на соседних границах для каждой задачи отдельно.

2. Перепутанная форма (A) ↔ (B). В условиях вида «минимизируй максимум» легко выбрать форму (A) — потому что слово «максимум» в условии тянет. На самом деле мы минимизируем значение, форма (B). Различение: какое значение оптимизируем — таков и тип «оптимума».

3. Нет доказательства монотонности. Бинпоиск работает только если предикат меняется ровно один раз. Если про монотонность «и так понятно» — почти наверняка пропущен крайний случай. Полезное упражнение: явно доказать монотонность на 2 строки в комментарии к функции can.

4. Неправильные границы $\textit{lo}$ и $\textit{hi}$. Слишком узкие — ответ может выпасть за пределы, шаблон вернёт неправильный результат. Слишком широкие — лишние итерации, в худшем случае переполнение mid. Правильный приём: $\textit{lo}$ — гарантированно достижимый (или явно недостижимый, если форма позволяет), $\textit{hi}$ — гарантированно достижимый (или явно недостижимый).

5. Переполнение mid = (lo + hi) / 2. При границах около $10^{18}$ сумма lo + hi переполняет long long. Запись lo + (hi - lo) / 2 или lo + (hi - lo + 1) / 2 (для формы A) — защищённая.

6. can(x) имеет асимптотику хуже, чем кажется. Например, проверка через сортировку внутри can даёт $O(n \log n)$ на каждую итерацию — итого $O(n \log n \cdot \log \textit{range})$. Часто это нормально, но в задачах с $n \cdot \log \textit{range} \sim 10^7$ — лимит уже жмёт. Если сортировку можно вынести за бинпоиск (отсортировать массив один раз) — это даёт ускорение на порядок.

7. Пропущенный вырожденный случай. «Что, если $k = 0$?» «Что, если массив пустой?» «Что, если сумма меньше $k$?» Бинпоиск как техника не защищает от вырожденных входов; их нужно отдельно проверять до запуска цикла или зашить в can.

8. Целочисленный бинпоиск с условием выхода через lo + 1 < hi. Иногда пишут такой шаблон, чтобы избежать вопроса об округлении mid. Это работает, но требует дополнительной финальной проверки — can(lo) и can(hi), выбрать правильный. Лишний шаг и лишний источник ошибок; форма «lo < hi» с правильным округлением — компактнее и реже ломается.

---

Когда бинпоиск по ответу НЕ подходит

Несколько ситуаций, когда техника выглядит подходящей, а на самом деле — нет.

• Предикат не монотонный. Если внутри диапазона ответа есть «плохие» точки между «хорошими», бинпоиск даст случайный результат — он лишь найдёт какую-то точку перехода, не обязательно правильную. Полезный тест: если на маленьких данных перебрать все $x$ и нарисовать «достижимость», нет ли несвязного множества true? Если есть — другая техника (DP, прямая конструкция, поток).

• Ответ — не число, а структура. «Найти раскраску графа с минимальным числом цветов» — ответ-число, но проверка «есть ли раскраска в $k$ цветов» — NP-полная задача. Бинпоиск переносит сложность в can; если can сама по себе сложна — техника не помогает.

• Проверка слишком дорогая. Если can работает за $O(n^2)$, а $n = 10^5$, шаблон вылетит за TL. Бинпоиск спасает только когда can сильно дешевле, чем «прямое решение».

• Узкий диапазон с дешёвым прямым решением. Если ответ — это $0/1$, или диапазон содержит 10 кандидатов — проще перебрать все, без шаблона.

• Множественные ответы. Если задача требует не одно число, а пару (две границы интервала, несколько разрезов и т.п.) — бинпоиск даёт только одно. Иногда выручает двойной бинпоиск (бинпоиск по одному параметру при фиксированном другом), но это уже отдельная техника.

---

Связанные техники

Бинпоиск по ответу — каркас, на который ложатся несколько соседних подходов.

• Жадный алгоритм — почти всегда внутри can. Доказательство «жадная стратегия оптимальна по числу подмассивов / шагов / ресурсу» — отдельный навык; статья «Жадные алгоритмы и exchange argument» из этой же серии раскрывает его подробно.

• Two pointers / скользящее окно — частая структура can в задачах про последовательности. Например, проверка «существует ли подсегмент с суммой $\ge x$ длины $\le L$» — естественно делается скользящим окном за $O(n)$.

• DP в can. Иногда проверка «достижим ли $x$» сама требует динамики. Например, «можно ли набрать сумму $\ge x$, выбрав не более $k$ непересекающихся подмассивов» — can решается DP за $O(nk)$. Тогда суммарная сложность $O(nk \log \textit{range})$ — годится для $n, k$ до $10^3$.

• Тернарный поиск. Когда функция «значение → ответ» не монотонна, а унимодальна (одна точка минимума или максимума) — бинпоиск не работает, но работает тернарный поиск (на каждом шаге сравнивает значения в двух средних точках). Шаблон похожий, идея другая.

• Параметрический поиск (поиск по двойному инварианту). Когда ответ — отношение $\frac{A}{B}$ двух сумм по выборке элементов (например, «найти подмножество с максимальным средним»), используется бинпоиск по значению дроби с проверкой через сведение к линейной оптимизации. Это уже полоса 1900–2200.

<PostSeries> ниже выведет соседние статьи серии «Алгоритмические основы» автоматически.

---

Итого

• Техника: угадай ответ половинным делением, проверь предикат can(x).
• Два сигнала из условия: «найти максимальный/минимальный $x$ при котором …» и «минимизировать максимум / максимизировать минимум».
• Две формы шаблона: (A) max-true с $mid = (lo + hi + 1)/2$; (B) min-true с $mid = (lo + hi)/2$. Округление зависит от формы — иначе зацикливание.
• Сложность: $O(\textit{can}(n) \cdot \log \textit{range})$. Обычно $\textit{can} = O(n)$ или $O(n \log n)$.
• Главный навык: не написать цикл, а выбрать инвариант и доказать монотонность. Цикл — четыре строки.
• Типичные ловушки: зацикливание из-за округления mid, перепутанная форма (A)↔(B), нечёткие границы $lo/hi$, дорогая can, переполнение mid.
• Связанные техники: жадные (внутри can), DP (внутри can для сложных проверок), скользящее окно, тернарный поиск (для унимодальных функций).