10837. Галька

 

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

Осенью, вспоминая тёплые дни, Антун и Бранка придумали игру с этими камешками. Сначала они выкладывают все n камешков в ряд. Затем игроки делают ходы по очереди: каждый раз необходимо убрать один камешек с одного из концов ряда. Проигрывает тот, кто первым наберёт k красных камешков. Антун всегда делает первый ход и задаётся вопросом: сможет ли он гарантировать победу, независимо от действий Бранки? Ваша задача – помочь ему ответить на этот вопрос.

 

Вход. Первая строка содержит два целых числа n и k (1 ≤ k < n ≤ 350).

Вторая строка содержит последовательность из n символов C или P, где C обозначает красный камешек, а P – синий. Гарантируется, что символ C встречается не менее чем 2 * k – 1 раз.

 

Выход. Выведите “DA”, если Антун может выиграть независимо от ходов Бранки, и “NE” в противном случае.

 

Пример входа 1

Пример выхода 1

4 1

CCCP

DA

 

 

Пример входа 2

Пример выхода 2

8 2

PCPPCCCC

DA

 

 

Пример входа 3

Пример выхода 3

9 1

PPCPPCPPC

NE

 

 

РЕШЕНИЕ

динамическое программирование

 

Анализ алгоритма

Поскольку символ C встречается не менее чем 2 * k – 1 раз, то игра обязательно закончится победой. Игра не закончится победой, если у каждого из участников будет не более k – 1 красных камней. То есть всего в игре должно быть не более 2k – 2 красных камней, что противоречит условию.

Построим массив prefix чтобы быстро находить количество красных камешков на любом подотрезке [l, r]:

prefix[0] = (str[0] == 'C')

prefix[i] = prefix[i-1] + (str[i] == 'C')

Тогда число красных камешков на подотрезке [l, r] можно вычислить за O(1):

red_left = prefix[r];

if (l) red_left -= prefix[l-1];

 

Рассмотрим следующую функцию:

int can_win(int l, int r, int uk)

·        Сейчас ходит Антун (первый игрок).

·        Подотрезок камней: с l по r.

·        У Антуна уже имеется uk красных камней.

·        Функция возвращает 1, если Антун может гарантировать победу в этой позиции, иначе 0.

 

Условия окончания игры:

·        Если uk >= k, то Антун уже набрал k, значит он проиграл.

·        Если у Бранки обязательно получится собрать k красных камней, то Антун выигрывает.

 

Игроки по очереди совершают ходы:

·        Антун может взять камень слева (l + 1) или справа (r – 1).

·        Чтобы Антун гарантировал себе победу, хотя бы один из его ходов должен привести к позиции, где у Бранки нет выигрышной стратегии.

 

if (!can_win(l + 1, r, other_red) || !can_win(l, r - 1, other_red))

  res = 1;

else

  res = 0;

 

Здесь other_red – количество красных камней, которые накопятся у Бранки. То есть мы моделируем ситуацию: “я хожу, потом ходит соперник”. Если имеется хотя бы один ход, после которого соперник гарантированно не выигрывает, то Антун выигрывает.

Значение other_red вычисляется следующим образом:

 

int total_red = prefix[n - 1]; // всего красных в строке

int red_left = prefix[r];    // красных до позиции r

if (l) red_left -= prefix[l - 1]; // красных на [l, r]

int other_red = total_red - red_left - uk;

 

·        red_left – сколько красных камней лежит в текущем интервале [l, r];

·        total_red – red_left – uk = сколько красных камней останется сопернику (Бранке), если Антун уже набрал uk.

 

Таким образом, игра сведена к рекурсивному DP по трём параметрам:

·        (l, r, uk) – подотрезок и число красных камней у Антуна.

Вызов функции и вывод результатов:

if (can_win(0, n - 1, 0))

  puts("DA");  // Антун может гарантировать победу

else

  puts("NE");  // нет

 

Реализация алгоритма

Объявим рабочие массивы:

·        prefix – префиксные суммы красных камешков.

·        dp – мемоизация для динамического программирования игры.

 

#define MAX 352

int prefix[MAX], dp[MAX][MAX][MAX];

 

Функция can_win возвращает 1, если игрок (Антун или Бранка) может гарантировать победу в этой позиции, иначе 0.

·        Сейчас ходит Антун / Бранка.

·        Подотрезок камней: с l по r.

·        У Антуна / Бранки уже имеется uk красных камней.

 

int can_win(int l, int r, int uk)

{

  int& res = dp[l][r][uk];

 

Если значение функции еще не вычислено.

 

  if (res == -1)

  {

 

Вычисляем сколько красных камней red_left лежит в интервале [l, r];

Вычисляем сколько красных камней total_red – red_left – uk останется сопернику (Бранке / Антуну), если Антун / Бранка уже набрал uk.

 

    int total_red = prefix[n - 1];

    int red_left = prefix[r];

    if (l) red_left -= prefix[l - 1];

    int other_red = total_red - red_left - uk;

 

Если uk >= k, то Антун / Бранка уже набрал k красных камней, значит он проиграл.

 

    if (uk >= k)

      res = 0;

 

Если у Бранки / Антуна обязательно получится собрать k красных камней, то Антун / Бранка выигрывает.

 

    else if (other_red >= k)

      res = 1;

    else

    {

 

Антун / Бранка может взять камень слева (l + 1) или справа (r – 1). Чтобы Антун гарантировал себе победу, хотя бы один из его ходов должен привести к позиции, где у Бранки / Антуна нет выигрышной стратегии.

 

      if (!can_win(l + 1, r, other_red) ||

          !can_win(l, r - 1, other_red))

        res = 1;

      else

        res = 0;

    }

  }

  return res;

}

 

Основная часть программы. Читаем входные данные.

 

memset(dp, -1, sizeof(dp));

cin >> n >> k;

cin >> str;

 

Вычисляем массив префиксов prefix.

·        prefix[i] содержит количество красных камней в позициях от 0 до i включительно.

 

prefix[0] = (str[0] == 'C');

for (i = 1; i < n; i++) prefix[i] = prefix[i - 1] + (str[i] == 'C');

 

Вызываем функцию и выводим результат:

 

if (can_win(0, n - 1, 0))

  cout << "DA" << endl;

else

  cout << "NE" << endl;