Блог пользователя natalia

Автор natalia, 14 лет назад, По-русски
В задаче описывается игра на ациклическом графе. Состояниями (вершинами графа) являются пары (n, m), где  n и m - расстояния от текущей позиции фигуры до нижнего и правого краев доски соответственно. Из каждого состояния (n, m) существует не более трех переходов: (n - 1, m), (n, m - 1), (n - k, m - k).  Граф ациклический, поскольку при каждом переходе сумма n+m строго уменьшается. 

Если бы n, m и k в задаче были, скажем, до 1000, то задача решалась бы несложной динамикой на ациклическом графе, стандартной для подобных игр. Пусть d(n, m) = 1, если (n, m) - выигрышная позиция, и d(n, m) = 0, если позиция (n, m) - проигрышная. Тогда d(n, m) вычисляется из следующих соображений: если из позиции существует хотя бы один переход в проигрышное состояние, то эта позиция выигрышная, иначе она проигрышная.

Но ограничения в задаче не позволяют решать ее обычной динамикой. Выход из ситуации - посчитать динамику для маленьких значений n и m и заметить закономерность! Например, построим матрицу значений d(n, m) при k = 2:

01010101010101
10101010101010
01111111111111
10110101010101
01101010101010
10110111111111
01101101010101
10110110101010
01101101............


Будем рассматривать угловые полосы на этой картинке. Начнем с угловой полосы шириной 2 в левом верхнем углу (полоса в данном случае - множество клеток при n <= 2 || m <= 2) .
Получается, что начиная с левого верхнего угла идет полоса ширины 2 (на самом деле k при k > 2), в которой 0 и 1 чередуются. Что неудивительно, потому что в этой полосе нет возможности прыжка на k. Дальше идет полоса из 1, затем - такая же полоса ширины k, как и первая, только инвертированная (1 заменены на 0, 0 на 1), затем - снова полоса из 1, и затем - снова такая же полоса, как и в самом начале! Поскольку каждая следующая угловая полоса зависит только от предыдущей полосы шириной k клеток, получается, что дальше закономерность будет повторяться: последует полоса из плюсов, инвертированная полоса, снова полоса из плюсов и т.д. Фактически получается, что d(n, m) = d(n - (2 k + 2), m - (2 k + 2)) при n, m > 2 k + 2. Отсюда можно получить формулы для вычисления d(n, m) при любых n и m. 

Чтобы лучше разобраться в приведенный объяснениях, советую написать программу подсчета динамики и поискать закономерность самостоятельно.

Есть еще один хитрый случай k = 1. Для него получается немного другая закономерность:)

Замечание. Особо подчеркну, что мы не просто нашли закономерность и выдвинули шаманскую гипотезу о том, что она будет повторяться. Мы это доказали. Полосы будут чередоваться дальше, потому что каждая следующая полоса однозначно определяется через предыдущую полосу шириной k клеток.
Разбор задач Codeforces Beta Round 36
  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

14 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

У меян была идея алгоритмического решения, она заключаласть в следующем:

пусть c = min(a-1,b-1)/k -- кол-во возможных ходов по диагонали. Если min( (a-1) % k , (b-1)%k ) >= c то ответ a+b+c % 2 == 1 , иначе второй игрок может испортить первому ситуацию, ходя в ту сторону, остаток от деления величины которой наименьший (диагонали теперь первому ходить не выгодно), и мы перейдем в следующее состояние, пусть для общности было a%k<b%k. Теперь  b %k=(b-a%k)%k; a%k=k-1 c--; a и б уменьшаются равномерно. будем делать динамику по остаткам числа a. их всего будет sqrt(n). возможно будут цикл в ДП надо найти его длину и ввеличину с взять по модулю его длины.

Хотелось бы спросить мнение сообщества по этому методу.

PS Извиняюсь за смутное изложение идеи. Не проснулся еще ))

PS2 Возможны ошибки +-1 и = != :o)

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Имхо. когда контест составляют многие люди сразу, то разбор получается никаким. Всё разбросано, в разностороннем стиле... Можно ведь как то скооперироваться. Иначе каша, 10 задач каждая в разном блоге. Спасибо за понимание, ведь хороший разбор тоже важная часть соревнования для многих людей.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Имхо. когда контест составляют многие люди сразу, то разбор получается никаким. Всё разбросано, в разностороннем стиле... Можно ведь как то скооперироваться. Иначе каша, 10 задач каждая в разном блоге. Спасибо за понимание, ведь хороший разбор тоже важная часть соревнования для многих людей.
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Нам было предъявлено требование писать каждый разбор отдельным постом, чтобы комментарии по одной задаче были в одном месте
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Неплохо бы было набрать эту кашу из плюсов и минусов моноширинным шрифтом(ну или вообще картинкой), а то так почти невозможно понять, что это за хитрая закономерность.