Бинпоиск по ответу с STL

Revision ru18, by Helgui, 2017-11-30 13:54:02

Привет, Codeforces! Сегодня мы попробуем решить пару задач на целочисленный бинпоиск по ответу с помощью std::lower_bound и поймем, что это бессмысленно, но красиво (на самом деле нет).

Начнем с задачи 535C - Тавас и Карафс, которая решается двоичным поиском (например, 32799258). В этой задаче по заданным l, t, m, A, B нужно найти такое наибольшее , что

Как известно, std::lower_bound(first, last, v, pred) возвращает итератор, указывающий на первое значение a такое, что pred(a, v) == false, или last, если такого значения нет. Если в качестве предиката использовать s(x) - s(l - 1) ≤ t·m, то ответом на задачу будет значение, предшествующее lower_bound'у.

Приступим. Диапазоном для бинпоиска будет служить массив range такой, что range[i] = i. Заполнить такой массив поможет std::iota из <numeric>.

const int N = 1000000;
int range[N + 5];
//...
iota(range, range + N, 0);

lower_bound заточен под бинарные предикаты, но у нас унарный. Значит, второй аргумент и искомое значение (третий параметр lower_bound) будут фиктивными. Оформим предикат в виде лямбды и получим такую функцию

inline int solve(int l, int t, int m) {
    int r = (t - A) / B + 1;
    i64 lim = i64(t)*m;
    if (r < l)            
        return -1;
    if (sum(l, l) > lim)
        return -1;
    return *lower_bound(range + l, range + r + 1, 0, [lim, l](int item, int) -> bool {
    	return sum(l, item) <= lim; //sum(l, item) - это s(item) - s(l - 1) из описания
    }) - 1;
}

Возможно, обработка случаев с -1 не требуется, но я её оставил от предыдущего решения. Полный вариант — 32800781. Время работы этого решения почти не отличается от самописного бинпоиска.

В рассмотренной задаче мы явно использовали то, что диапазон бинпоиска небольшой, и его можно целиком хранить в массиве. Но что делать, если границы имеют порядок 109 или даже 1018? В этом случае придется реализовать итератор для целочисленного диапазона, использующий O(1) памяти, который удовлетворяет интерфейсу RandomAccessIterator. Например, так (много кода):

class Range{...}

Этот вариант опробуем на задаче 760B - Фродо и подушки (спасибо -Morass- за Problem Topics). В этой задаче по заданным n, m, k небходимо найти такое наибольшее , что

s(x, k - 1) + s(x, n - k) + x ≤ m

Оформим все аналогично предыдущей задаче и получим такое решение c использованием Range:

//...
typedef long long i64;

inline i64 pillows(i64 x, i64 y) {
	if (y > x -; 1) {
		return (x*(x - 1)) / 2 + y - (x - 1);
	}
	return ((2*x - y - 1)*y) / 2;
}

int main() {
	i64 n, m, k;
	cin >> n >> m >> k;
	Range range(1, m);
	cout << (*lower_bound(range.begin(), range.end(), 0, [n, m, k](long long x, int) -> bool {
		return pillows(x, k - 1) + pillows(x, n - k) + x <= m; 		
	}) - 1);
	return 0;
}

Полный вариант — 32802235.

Очевидно, что вариант с Range имеет смысл только тогда, когда есть возможность заинлайнить (с помощью JHelper и подобных инструментов) написанный ранее класс Range. Но в этом случае можно заинлайнить и написанный ранее шаблонизированный бинпоиск, получив исходник меньшего размера и более быстрое (хоть и незначительно) решение. Таким образом, практическое применение lower_bound в задачах на бинпоиск по ответу имеет смысл только при небольшом размере диапазона.

Tags binary search, stl, двоичный поиск, бин. поиск, lower_bound

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru22 Russian Helgui 2017-11-30 13:59:01 4 Мелкая правка: 'terator`. Например, ' -> 'terator`. \n\nНапример, '
ru21 Russian Helgui 2017-11-30 13:58:17 0 (опубликовано)
ru20 Russian Helgui 2017-11-30 13:57:48 8
ru19 Russian Helgui 2017-11-30 13:57:06 16 Мелкая правка: 'диапазона.\n\n\n\n\n\n\n\n' -> 'диапазона.'
ru18 Russian Helgui 2017-11-30 13:54:02 29
ru17 Russian Helgui 2017-11-30 13:53:11 71
ru16 Russian Helgui 2017-11-30 13:51:41 4 Мелкая правка: 'le m\n$$\n$$\n\mbo' -> 'le m\n$$\n\n\n$$\n\mbo'
ru15 Russian Helgui 2017-11-30 13:51:07 32
ru14 Russian Helgui 2017-11-30 13:49:03 24 Мелкая правка: 'й вариант решения с `lower_bound` &mdash; [' -> 'й вариант &mdash; ['
ru13 Russian Helgui 2017-11-30 13:47:32 40
ru12 Russian Helgui 2017-11-30 13:46:05 16 Мелкая правка: ' аргумент будет фиктивным и искомое' -> ' аргумент и искомое'
ru11 Russian Helgui 2017-11-30 13:43:54 2 Мелкая правка: 'ее $x \in (l, \lfloor' -> 'ее $x \in [l, \lfloor'
ru10 Russian Helgui 2017-11-30 13:43:17 534
ru9 Russian Helgui 2017-11-30 13:33:16 899 Мелкая правка: '\mbox{где ] s(x, y) =' -> '\mbox{где } s(x, y) ='
ru8 Russian Helgui 2017-11-30 13:06:40 33
ru7 Russian Helgui 2017-11-30 13:00:23 147
ru6 Russian Helgui 2017-11-30 12:55:06 2140
ru5 Russian Helgui 2017-11-30 12:43:54 1180
ru4 Russian Helgui 2017-11-30 11:53:38 274 Мелкая правка: 'e t \cdot m\n\n$$' -> 'e t \cdot \n$$'
ru3 Russian Helgui 2017-11-30 11:36:10 155
ru2 Russian Helgui 2017-11-30 11:30:14 2 Мелкая правка: 'roblem:535С], которая' -> 'roblem:535C], которая'
ru1 Russian Helgui 2017-11-30 11:29:52 306 Первая редакция (сохранено в черновиках)