Галька#10837

Галька (Розбір)

Оскільки символ $C$ зустрічається не менше ніж $2 \cdot k - 1$ 2 \cdot k - 1 разів, то гра обов'язково закінчиться перемогою. Гра не закінчиться перемогою, якщо кожен з учасників матиме не більше $k - 1$ k - 1 червоних каменів. Тобто всього в грі повинно бути не більше $2 k - 2$ 2k - 2 червоних каменів, що суперечить умові.

Побудуємо масив $p r e f i x$ prefix щоб швидко знаходити кількість червоних камінців на будь-якому підвідрізку $[l, r]$ [l, r]:

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

Тоді число червоних камінців на підвідрізку $[l, r]$ [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$ .
У Антуна вже є $u k$ червоних каменів.
Функція повертає $1$ , якщо Антун може гарантувати перемогу в цій позиції, інакше $0$ .

Умови закінчення гри:

Якщо $u k \geq k$ uk \ge k, то Антун вже набрав $k$ червоних каменів, значить він програв.
Якщо у Бранки обов'язково вийде зібрати $k$ червоних каменів, то Антун виграє.

Гравці по черзі здійснюють ходи:

Антун може взяти камінь зліва $(l + 1)$ (l + 1) або справа $(r - 1)$ (r - 1).
Щоби Антун гарантував собі перемогу, хоча б один із його ходів повинен привести до позиції, де у Бранки немає виграшної стратегії.

if (!can_win(l + 1, r, other_red) || !can_win(l, r - 1, other_red))
  res = 1;
else
  res = 0;

Тут $o t h er_r e d$ other\_red — кількість червоних каменів, які накопичаться у Бранки. Тобто ми моделюємо ситуацію: "я ходжу, потім ходить супротивник". Якщо є хоча б один хід, після якого супротивник гарантовано не виграє, то Антун виграє.

Значення $o t h er_r e d$ 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;

$r e d_l e f t$ red\_left — скільки червоних каменів лежить у поточному інтервалі $[l, r]$ [l, r];
$t o t a l_r e d - r e d_l e f t - u k$ total\_red - red\_left - uk = скільки червоних каменів залишиться супротивнику (Бранці), якщо Антун вже набрав $u k$ .

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

$(l, r, u k)$ (l, r, uk) — підвідрізок і кількість червоних каменів у Антуна.

Виклик функції і виведення результатів:

if (can_win(0, n - 1, 0))
  puts("DA");  // Антун може гарантувати перемогу
else
  puts("NE");  // ні

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

Оголосимо робочі масиви:

$p r e f i x$ prefix — префіксні суми червоних камінців.
$d p$ — мемоізація для динамічного програмування гри.

#define MAX 352
int prefix[MAX], dp[MAX][MAX][MAX];

Функція can_win повертає $1$ , якщо гравець (Антун або Бранка) може гарантувати перемогу в цій позиції, інакше $0$ .

Зараз ходить Антун / Бранка.
Підвідрізок каменів: від $l$ до $r$ .
У Антуна / Бранки вже є $u k$ червоних каменів.

int can_win(int l, int r, int uk)
{
  int& res = dp[l][r][uk];

Якщо значення функції ще не обчислено.

  if (res == -1)
  {

Обчислюємо скільки червоних каменів $r e d_l e f t$ red\_left лежить у інтервалі $[l, r]$ [l, r];

Обчислюємо скільки червоних каменів $t o t a l_r e d - r e d_l e f t - u k$ total\_red - red\_left - uk залишиться супротивнику (Бранці / Антуну), якщо Антун / Бранка вже набрав $u k$ .

    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;

Якщо $u k \geq k$ uk \ge k, то Антун / Бранка вже набрав $k$ червоних каменів, значить він / вона програв.

    if (uk >= k)
      res = 0;

Якщо у Бранки / Антуна обов'язково вийде зібрати $k$ червоних каменів, то Антун / Бранка виграє.

    else if (other_red >= k)
      res = 1;
    else
    {

Антун / Бранка може взяти камінь зліва $(l + 1)$ (l + 1) або справа $(r - 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;
}

C++

Основна частина програми. Читаємо вхідні дані.

memset(dp, -1, sizeof(dp));
cin >> n >> k;
cin >> str;

Обчислюємо масив префіксів $p r e f i x$ prefix.

$p r e f i x [i]$ 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;