Игры: Гранди, Ретроанализ

  1. [Сережа.K] Доказательство Skew heap
  2. [Сережа.М] Ретроанализ
    1. Ацикличный граф: решение динамикой за O(E)
    2. Цикличный граф: решение за O(VE)
    3. Цикличный граф: ретроанализ за O(E)
  3. [Сережа.М] Эквивалентность
    1. ∀C : res(A+C) = res(B+C)
    2. Все проигрышные эквивалентны
    3. Любая игра эквивалентна Ниму ⇒ mex
  4. [Сережа.М] Гранди
    1. Ним: xor выигрывает с доказательством
    2. Определяем функцию Гранди: mex
    3. Замечаем, если она ноль, то LOSE, иначе WIN
    4. Учимся считать Гранди за O(E)
    5. Доказываем, что Гранди от суммы игр равна XOR.
    6. Рисуем табличку: Функция Гранди для суммы двух Нимов
  5. [Сережа.М] Задачи
    1. Ретроанализ
      1. На графе с ребрами двух цветов
      2. Который считает кратчайший выигрышный путь
      3. Который считает наидлиннейший выигрышный путь
    2. Гранди
      1. Пешки на доске 3 × N для N ≥ 109
      2. Hucking Bush: Grundi(1+T) = 1+Grundi(T)
      3. Ним в поддавки
      4. Ним, в котором кучки должны иметь неубывающие размеры
      5. Ним, в котором брать можно из не более чем двух кучек за ход (как факт, без доказательства)