Çınqıl#10837

Çınqıl (Həll təhlili)

Simvol $C$ ən azı $2 \cdot k - 1$ 2 \cdot k - 1 dəfə təkrarlanır. Bu halda oyun mütləq qalibiyyətlə bitəcək. Oyun yalnız hər bir iştirakçının $k - 1$ k - 1-də çox qırmızı daş əldə etməməsi halında qalibiyyətlə bitə bilməz. Yəni oyunda $2 k - 2$ 2k - 2-dən artıq qırmızı daş ola bilməz ki, bu da şərtlərə ziddir.

$p r e f i x$ prefix adlı massiv quraraq istənilən $[l, r]$ [l, r] altmərhələsində qırmızı daşları tez bir zamanda tapmaq:

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

Bu halda $[l, r]$ [l, r] altmərhələsində qırmızı daşların sayını $O (1)$ zamanında hesablamaq olar:

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

Aşağıdakı funksiyanı nəzərdən keçirək:

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

İndi Anton (birinci oyunçu) növbədədir.
Daşların altmərhələsi: $l$ -dən $r$ -ə.
Anton artıq $u k$ qırmızı daş əldə edib.
Funksiya $1$ qaytarırsa, Anton bu mövqedə qalibiyyəti təmin edə bilər, əks halda $0$ .

Oyunun son şəraiti:

Əgər $u k \geq k$ uk \ge k, Anton artıq $k$ qırmızı daş əldə edib, deməli o uduzdu.
Əgər Branka mütləq $k$ qırmızı daş toplaya bilərsə, Anton qalib gəlir.

Oyunçular növbəli olaraq hərəkət edirlər:

Anton daşları sol tərəfdən $(l + 1)$ (l + 1) və ya sağ tərəfdən $(r - 1)$ (r - 1) götürə bilər.
Anton qalibiyyəti təmin etmək üçün onun hərəkətlərindən biri Brankanın qələbə strategiyası olmadığı bir vəziyyət yaradırsa.

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

Burada $o t h er_r e d$ other\_red — Branka tərəfindən toplanacaq qırmızı daşların sayıdır. Yəni "mən hərəkət edirəm, sonra rəqib hərəkət edir" vəziyyətini modelləşdiririk. Əgər Antonun rəqibinin mütləq qalib gəlməyəcəyi bir hərəkəti olsa, Anton qalib gəlir.

$o t h er_r e d$ other\_red aşağıdakı kimi hesablanır:

int total_red = prefix[n - 1]; // sıralamada ümumi qırmızı daşlar
int red_left = prefix[r];    // r mövqeyine qədər qırmızı daşlar
if (l) red_left -= prefix[l - 1]; // [l, r] üzərində qırmızı daşlar
int other_red = total_red - red_left - uk;

$r e d_l e f t$ red\_left — cari intervalda $[l, r]$ [l, r] neçə qırmızı daş var;
$t o t a l_r e d - r e d_l e f t - u k$ total\_red - red\_left - uk = Anton artıq $u k$ yığmışsa, rəqibə (Branka) neçə qırmızı daş qalacaq.

Bu sayədə oyun üç parametr üzrə rekursiv DP-yə çevrilmişdir:

$(l, r, u k)$ (l, r, uk) — altmərhələ və Antonun qırmızı daşlarının sayı.

Funksiyanı çağırmaq və nəticələri göstərmək:

if (can_win(0, n - 1, 0))
  puts("DA");  // Anton qalibiyyətini təmin edə bilər
else
  puts("NE");  // yox

Alqoritmanın həyata keçirilməsi

İş massivlərini elan edək:

$p r e f i x$ prefix — qırmızı daşların prefix summaları.
$d p$ — oyun üçün dinamik proqramlaşdırma memoriasiyası.

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

can_win funksiyası bu mövqedə olan oyunçu (Anton və ya Branka) qalibiyyəti qarantiləşdirə bilərsə $1$ , əks halda $0$ qaytarır.

İndi Anton / Branka növbədədır.
Daşların altmərhələsi: $l$ -dən $r$ -ə.
Anton / Branka artıq $u k$ qırmızı daş əldə edib.

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

Əgər funksiyanın dəyəri hələ də hesablanmayıbsa.

  if (res == -1)
  {

İntervalda $[l, r]$ [l, r] qırmızı daşların $r e d_l e f t$ red\_left sayını hesablayırıq;

İntervalda Anton / Branka artıq $u k$ toplamışsa, rəqibin (Branka / Anton) qalan qırmızı daşların $t o t a l_r e d - r e d_l e f t - u k$ total\_red - red\_left - uk sayını hesablayırıq.

    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;

Əgər $u k \geq k$ uk \ge k, Anton / Branka artıq $k$ qırmızı daş toplamışdır, deməli o / o uduzdu.

    if (uk >= k)
      res = 0;

Əgər Branka / Anton mütləq $k$ qırmızı daş toplaya bilirsə, Anton / Branka qalib gəlir.

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

Anton / Branka daşları sol tərəfdən $(l + 1)$ (l + 1) və ya sağ tərəfdən $(r - 1)$ (r - 1) götürə bilər. Anton qalibiyyəti təmin etmək üçün onun hərəkətindən biri Branka / Anton qalibiyyət strategiyası olmadığı bir mövqe yaradırsa.

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

C++

Proqramın əsas hissəsi. Daxil olan məlumatları oxuyuruq.

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

$p r e f i x$ prefix massivini hesablayırıq.

$p r e f i x [i]$ prefix[i] mövqedən $0$ -dan $i$ -yə qədər olan qırmızı daşların sayını ehtiva edir.

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

Funksiyanı çağırırıq və nəticəni göstəririk:

if (can_win(0, n - 1, 0))
  cout << "DA" << endl;
else
  cout << "NE" << endl;