Автор задачі: | Костянтин Денисов |
Задачу підготував: | Данило Квіт |
Розбір написав: | Костянтин Денисов |
Твердження. Позначимо \operatorname{cnt}(l, r) — кількість різних цифр на відрізку [l, r] рядка . Якщо існує відрізок [l, r] для якого виконується нерівність \operatorname{cnt}(l, r) \cdot 2 \le r - l + 1, то гарантовано у грі виграє другий гравець.
Доведення.
Доведемо це твердження методом математичної індукції за довжиною відрізка [l, r].
База індукції. Розглянемо випадок, коли 2 \le r - l + 1 \le 3. У цьому випадку всі цифри на відрізку однакові (тобто s_l = s_{l+1}), а отже, другий гравець завжди перемагає.
Індуктивний перехід. Припустимо, що твердження справедливе для всіх відрізків довжини менше ніж r - l + 1. Доведемо його для відрізка [l, r], де \operatorname{cnt}(l, r) \cdot 2 \le r - l + 1.
Розглянемо величину [ d = r - l + 1 - 2 cnt(l, r). ]
Тепер обмежимо гру лише цим відрізком і припустимо, що перший гравець може робити ходи поза відрізком, але це не вплине на нашу стратегію.
Як змінюється за один хід?
Довжина r - l + 1 може зменшитися на (або не змінитися, якщо хід зроблено поза відрізком).
\operatorname{cnt}(l, r) або залишається незмінною, або зменшується на (якщо видалено цифру, яка зустрічалася лише раз).
Отже, у найгіршому випадку зменшується на за хід.
Тепер розглянемо три випадки залежно від значення після ходу першого гравця:
d \ge 1. Після будь-якого ходу другого гравця d \ge 0;
d = -1. У цьому випадку на відрізку обов'язково існує цифра, яка зустрічається рівно один раз (інакше d \ge 0). Другий гравець може видалити цю цифру, і стане рівним ;
d = 0. Якщо є цифра, яка зустрічається лише раз, другий гравець також видалить її і перейде до виграшного стану. Інакше усі цифри зустрічаються рівно рази. Тоді розглянемо підвідрізок [l+1, r]. На цьому підвідрізку величина дорівнює , і обов'язково існує цифра, що зустрічається один раз. Другий гравець видаляє її та переходить у виграшний стан.
В усіх випадках кількість цифр на відрізку зменшується, а припущення індукції дозволяє завершити гру на користь другого гравця.
Рядок складається лише з цифр, тому \operatorname{cnt}(l, r) \le 10. Тоді, якщо |s| \ge 20, то з нашого твердження маємо, що гарантовано виграє другий. Тепер треба визначити, хто виграє для |s| < 20.
Для коротших рядків (|s| < 20) можна скористатися рекурсією з мемоізацією:
Кожен стан гри описується бітовою маскою , де mask_i = 1, якщо -ту цифру ще не видалено, і mask_i = 0, якщо видалено;
Усього можливих станів — 2^{|s|};
Для кожного стану перебираємо можливі ходи і рекурсивно визначаємо переможця.
Складність алгоритму O(2^{|s|} \cdot |s|).