Хвост суммы кубиков
В настольной игре бросают n обычных шестигранных кубиков. Приз дают, если сумма очков не меньше s. Организатор хочет напечатать на коробке вероятность выиграть — для каждого варианта правил. Некоторые варианты почти безнадёжны: при ста кубиках и s = 600 нужно, чтобы на всех выпала шестёрка. Вероятности бывают меньше 10⁻²⁰⁰, и печатать их решили десятичным логарифмом.
Вход
В первой строке число вариантов q (1 ≤ q ≤ 10 000). В каждой из следующих q строк — целые n и s (1 ≤ n ≤ 300, n ≤ s ≤ 6n).
Выход
Для каждого варианта — десятичный логарифм вероятности того, что сумма n кубиков не меньше s. Ответ принимается с абсолютной или относительной погрешностью 10⁻⁶.
Примеры
Пример 1
4 1 6 2 12 10 35 100 600
-0.778151250 -1.556302501 -0.270554628 -77.815125038
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 5 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Первая мысль — разыграть броски много раз и посчитать долю удач. Сколько бросков нужно, чтобы хоть раз увидеть сто шестёрок подряд, если вероятность этого 6⁻¹⁰⁰ ≈ 10⁻⁷⁸?
2Подсказка 2
Вторая мысль — сумма многих кубиков распределена почти нормально, и хвост можно взять у нормального закона. Это верно около середины, но с какой относительной точностью — в хвосте?
3Идея
Ни симуляция, ни нормальное приближение здесь не годятся: относительная ошибка Монте-Карло для вероятности p — около 1/√(np), а у нормального приближения ошибка в далёком хвосте — десятки порядков. Число исходов можно посчитать точно. Пусть ways[t] — сколькими способами k кубиков дают сумму t. Добавим ещё один кубик: новая сумма t получается из старой t − 1, …, t − 6. Это динамика по числу кубиков, а нужная вероятность — сумма хвоста ways[s] + … + ways[6n], делённая на 6n.
4Разбор
В Python числа способов можно держать целыми: 6³⁰⁰ — число из 234 цифр, длинная арифметика справится, и ответ получится без единой ошибки округления. Логарифм берём от целых: math.log10(tail) - n * math.log10(6) — log10 умеет работать с целыми любой длины. Новый слой считается окном из шести: сумма окна сдвигается на одну клетку прибавлением одного числа и вычитанием другого.
В Go удобнее вероятности в float64: 6⁻³⁰⁰ ≈ 10⁻²³⁴ ещё помещается в double. Но здесь есть ловушка. Скользящее окно в дробных числах — прибавить одно, вычесть другое — в далёком хвосте вычитает из 0,1 почти те же 0,1 и оставляет мусор порядка 10⁻¹⁷ вместо 10⁻²⁰⁰, а то и отрицательное число, от которого логарифм даст NaN. Поэтому шесть слагаемых складываем напрямую, а хвост суммируем от больших t к меньшим: маленькие числа складываются с маленькими.
Решение строит слои для всех n до наибольшего в запросах один раз и отвечает на каждый запрос из готовых хвостов.
4+Решение
5Сложность
Слоёв 300, в каждом до 1800 сумм по 6 слагаемых: около трёх миллионов действий. В Python с длинными числами это доли секунды. Для тысяч кубиков слой можно возводить в степень через свёртку и быстрое преобразование Фурье.
6Типичные ошибки
- Монте-Карло. Миллион бросков ста кубиков никогда не покажет сумму 600 — оценка ноль, логарифм минус бесконечность.
- Нормальный закон. Для ста кубиков и s = 600 он даёт 10⁻⁴⁸ вместо 10⁻⁷⁸ — ошибка в 10³⁰ раз. Даже около середины точности 10⁻⁶ у него нет.
- Скользящее окно в float. Взаимное уничтожение близких чисел — см. разбор: в хвосте получаются нули и отрицательные вероятности.
- 6ⁿ в целых Go. Уже 6²⁵ не помещается в 64 бита.
Алгоритмы задачи
O(n) испытаний, ошибка ~ σ/√n
2 задачи
DP
Приём
Динамическое программирование
Сводим задачу к подзадачам, решаем каждую один раз и храним ответы в таблице.
состояния × переходы
2 задачи
TEC
Приём
Префиксные суммы
Сумма любого отрезка за O(1) после одного прохода; двумерный вариант считает сумму любого прямоугольника картинки.
O(n) на построение, O(1) на запрос
2 задачи