DP Динамическое программирование Приём
Динамика по цифрам
Также: Digit DP · digit dynamic programming · счастливые билеты · lucky tickets · подсчёт чисел в диапазоне · числа с условием на цифры · tight
Сколько чисел от L до R обладают свойством, которое проверяется по цифрам: сумма, соседние цифры, остаток. Перебор номеров стоит R − L, а проход по цифрам числа R с таблицей «сколькими способами закончить» — десятки операций даже для 10¹⁸.
Шестизначный билет счастливый, если сумма первых трёх цифр равна сумме последних трёх. Из миллиона номеров счастливых 55 252 — примерно каждый восемнадцатый. Ровно столько же шестизначных строк с суммой цифр 27, и это не совпадение. Сколько счастливых среди номеров до вашего, можно узнать, не перебирая номера: достаточно пройти по шести цифрам вашего номера и на каждой взять число из небольшой таблицы. Тем же проходом считаются счастливые билеты из восемнадцати цифр, а их 10¹⁸ номеров.
У билета 123456 следующий счастливый — 123501, и до него 5541 счастливый билет. Среди номеров от 700000 до 700999 счастливых всего 36: левая половина в этой тысяче одна и та же, 700 с суммой 7, а правых половин с суммой 7 ровно 36.
Идея
Перебор проверяет каждый номер. Динамика по цифрам считает номера пачками. Возьмём номер x и пойдём по его цифрам слева. На первой позиции можно поставить цифру меньше первой цифры x — и тогда все номера с таким началом точно меньше x, а остальные цифры любые. Сколько среди них счастливых, зависит только от того, что уже набрано: от суммы поставленных цифр. Это число берётся из таблицы. А можно поставить саму первую цифру x — тогда идём ко второй позиции «впритык», и всё повторяется.
Количество хороших номеров от 0 до x — сумма по позициям: для каждой цифры d меньше цифры x на этой позиции — сколько хороших окончаний у начала «цифры x до этой позиции, потом d». Это зависит только от короткого состояния — суммы, остатка, предыдущей цифры, — и считается таблицей заранее. Ответ для диапазона [L, R] — разность ответов для R и L − 1.
Для счастливых билетов таблица — ways[r][b]: сколькими способами записать r цифр с суммой b. Строится она как рюкзак: ways[r][b] — сумма ways[r − 1][b − d] по цифре d от 0 до 9. Число троек цифр с суммой s — это cs = ways[3][s], а счастливый билет — две тройки с одной суммой, поэтому всех счастливых Σ cs² = 55 252.
Каждый номер y < x той же длины попадает ровно в одну ветку прохода: на первой позиции, где цифры y и x различаются, цифра y меньше, и y учтён в ветке этой позиции и этой цифры.
Номера одной длины сравниваются как строки: y < x ровно тогда, когда на первой позиции i, где они различаются, цифра y меньше. До позиции i цифры y совпадают с цифрами x — это и есть путь «впритык», — на позиции i стоит d < xi, а дальше любые цифры: так устроена ветка (i, d). В другую ветку y попасть не может: у неё либо другая первая позиция расхождения, либо другая цифра на ней. Сам x проверяется отдельно, в конце пути.
Счастливых шестизначных билетов столько же, сколько шестизначных строк с суммой цифр 27.
Заменим в билете каждую цифру d правой половины на 9 − d. Это взаимно однозначное отображение строк на строки: применённое дважды, оно возвращает исходную. Сумма правой половины b переходит в 27 − b. Билет счастливый, когда сумма левой a равна b, то есть когда в новой строке сумма цифр a + 27 − b = 27.
Код
Таблица ways строится один раз. lucky_up_to(x, n) идёт по 2n цифрам x: в левой половине ветка цифры d оставляет свободными ещё несколько цифр левой и всю правую, и счастливых в ней столько, сколько пар «окончание левой с суммой t, правая с суммой (набрано + d + t)». В правой половине ветке нужно добрать до нуля разность, и это одно число из таблицы. Следующий счастливый билет — двоичный поиск по количеству.
Числа 10, 670, 55 252, 4 816 030… — сколько счастливых билетов из 2, 4, 6, 8 цифр. Билетов из восемнадцати цифр 10¹⁸, а счастливых среди них 32 458 256 583 753 952, около 3,2 %: чем длиннее половины, тем реже совпадают суммы.
Сколько это стоит
Проход по цифрам — D позиций по 10 цифр, и на каждой одно-два обращения к таблице; таблица — D × 9D чисел. Перебор растёт с количеством номеров.
Миллион номеров перебор на Python проходит почти за две секунды, по цифрам — за десятые доли миллисекунды. Для 10¹⁸ номеров подсчёт по цифрам занимает около миллисекунды, а перебор занял бы десятки тысяч лет.
Где легко ошибиться
- Граница включительно. Проход считает номера, строго меньшие x; сам x надо проверить отдельно. Иначе ответ для [L, R] теряет R.
- L − 1 при L = 0. Количество до −1 — ноль, а не проход по цифрам числа −1.
- Ведущие нули. У билетов они значимы — 000001 тоже билет. У обычных чисел нет: если условие касается «соседних цифр», число 7 не начинается с нулей, и состояние «ещё ничего не поставлено» нужно отдельно.
- Состояние слишком бедное. В ветке должно быть известно всё, от чего зависит, хороши ли окончания: для билетов — разность сумм, для запрета «13» — была ли предыдущая цифра единицей. Забытый признак даёт уверенный неверный ответ.
- Переполнение. Счастливых 18-значных 3,2 · 10¹⁶ — в 64 бита помещается, а произведения в промежуточных суммах лучше проверить заранее.
Где работает
Любой подсчёт «сколько чисел от L до R таких, что…», если свойство проверяется слева направо с небольшой памятью: сумма или произведение цифр, запрещённые сочетания, делимость (остаток — тоже состояние), числа, делящиеся на сумму своих цифр. С двоичным поиском по количеству — k-е такое число: например, номер этажа на кнопке лифта, если номера с четвёркой и с «13» пропускают. Тот же приём работает в других системах счисления и для строк с запретами — это подсчёт путей в автомате, читающем цифры.
Задачи
Счастливые билеты из 2n цифр в диапазонах номеров. И лифт без четвёрок и тринадцатого: какой номер на кнопке у N-го этажа.
Счастливые в диапазоне Лифт без четвёрок