Digital Game#378

Digital Game (Editorial)

Автор задачі:

Костянтин Денисов

Задачу підготував:

Данило Квіт

Розбір написав:

Костянтин Денисов

Твердження. Позначимо \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) або залишається незмінною, або зменшується на (якщо видалено цифру, яка зустрічалася лише раз).

Отже, у найгіршому випадку зменшується на за хід.

Тепер розглянемо три випадки залежно від значення після ходу першого гравця:

  1. d \ge 1. Після будь-якого ходу другого гравця d \ge 0;

  2. d = -1. У цьому випадку на відрізку обов'язково існує цифра, яка зустрічається рівно один раз (інакше d \ge 0). Другий гравець може видалити цю цифру, і стане рівним ;

  3. 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|).