Выигрышные и проигрышные позиции

Двое играют по очереди, ходы определены правилами, проигрывает тот, кто не может сходить. Оба играют идеально. Кто выиграет?

Это динамика: состояние — позиция, значение — исход при верной игре. Особенность в том, что значение булево, а переход формулируется через два коротких правила.

Два правила

Позиция называется выигрышной, если ходящий из неё побеждает при верной игре, и проигрышной — если проигрывает при любой своей игре.

1. Позиция выигрышная, если есть хоть один ход в проигрышную.
2. Позиция проигрышная, если все ходы ведут в выигрышные (в частности, если ходов нет вовсе).

Обратите внимание на несимметричность: для выигрыша достаточно одного хорошего хода, для проигрыша нужно, чтобы все ходы были плохи. Отсюда и код: цикл с досрочным выходом.

vector<char> win(n + 1, 0);
for (int i = 1; i <= n; i++)
    for (int step : moves)
        if (i >= step && !win[i - step]) { win[i] = 1; break; }

База — win[0] = 0: тому, кто не может сходить, засчитывается поражение. Если правила говорят иначе («кто взял последний камень, проиграл»), меняется ровно эта строка.

Пример: берут от 1 до k

В куче $n$ камней, за ход берут от 1 до $k$. Кто взял последний, выиграл.

Проверено: проигрышные позиции — ровно кратные $k + 1$, для $k$ от 1 до 8 и $n$ до 300.

Это тот редкий случай, когда динамика не нужна: ответ — одно сравнение n % (k + 1) != 0. Стратегия видна и без неё: дополняй ход противника до $k+1$, и куча всегда уменьшается ровно на $k+1$.

Но заметьте порядок работы: сначала посчитали таблицу, потом увидели закономерность. Это стандартный приём на олимпиаде — написать медленную динамику, распечатать проигрышные позиции и посмотреть на них глазами.

Пример: берут 1, 3 или 4

Ходы уже не подряд идущие, и простой формулы ждать неоткуда. Считаем таблицу и печатаем проигрышные позиции:

0, 2, 7, 9, 14, 16, 21, 23, 28, 30, ...

Видна периодичность с шагом 7. Проверено: до $n = 60$ проигрышные позиции — ровно те, у которых $n \bmod 7 \in \{0, 2\}$.

Это общее свойство: у игры с конечным набором ходов последовательность исходов всегда периодична, начиная с некоторого момента. Поэтому приём «посчитать первые сто значений и найти период» работает почти всегда — но период надо проверять, а не угадывать по первым пяти членам.

Когда исход не булев

Если игроки не просто выигрывают, а набирают очки, значением становится число.

Задача: в ряд лежат числа, за ход берут крайнее слева или крайнее справа. Каждый максимизирует свою сумму. На сколько выиграет первый?

Приём — хранить разность очков ходящего и его противника. Тогда позиция описывается отрезком, а ход меняет знак:

$$d[l][r] = \max\big(a_l - d[l+1][r],\ a_r - d[l][r-1]\big)$$

Минус здесь — вся суть: после нашего хода ходит противник, и его выгода — наш проигрыш.

for (int i = 0; i < n; i++) d[i][i] = a[i];
for (int len = 2; len <= n; len++)
    for (int l = 0; l + len - 1 < n; l++) {
        int r = l + len - 1;
        d[l][r] = max(a[l] - d[l + 1][r], a[r] - d[l][r - 1]);
    }

Проверено: на 20 000 наборах до десяти чисел (включая отрицательные) совпадает с полным перебором ходов.

Это динамика по подотрезкам — тот же порядок обсчёта по возрастанию длины.

Чего здесь нет

Игры, где позиция распадается на независимые части (несколько куч сразу), считаются не так: там нужна теория Шпрага — Гранди, и значением состояния становится не булев исход, а число. Это отдельная тема, и в базовых задачах она встречается редко.

Практическая граница простая: если позиция — одно число или один отрезок, хватает правил выше. Если позиция — набор независимых игр, ищите Гранди.

Как подступаться

1. Определить, что такое позиция, и убедиться, что ходы её уменьшают — иначе динамика зациклится.
2. Выписать базу: кто проигрывает, когда ходов нет.
3. Посчитать таблицу для маленьких $n$ и распечатать.
4. Поискать закономерность. Нашлась — проверить её на таблице большего размера, а не поверить на слово.
5. Не нашлась — сдавать таблицу, если ограничения позволяют.

Четвёртый пункт стоит отдельного предупреждения. Красивая гипотеза, подтверждённая на десяти значениях, ломается на сотне чаще, чем хочется. Проверка — три строки кода, и она обязательна.