[Baekjoon - 18694] Game of Nim Everywhere

난이도: Platinum I

 

태그

• NIM Game
• Bitmask
• Divide and Conquer

 

풀이

1. 1번 플레이어가 패배할 조건은?

님 게임에서 패배하는 경우는, 모든 Heap의 xor 합이 0일 때입니다.

지금 문제에서는 Heap이 N, 2N, 3N이므로, \( N \oplus 2N \oplus 3N = 0 \)인 경우겠죠.

그런데, \( 3N = N + 2N = (N \& 2N) \ll 1 + N \oplus 2N \)입니다.

 

\( N \oplus 2N \oplus ((N \& 2N) \ll 1 + N \oplus 2N) = 0 \)을 만족하려면, \( N \& 2N = 0 \)이어야 합니다.

 

이는 \( N \)과 \( 2N \)에 동시에 켜진 비트가 없어야 한다는 것을 의미하고,

\( 2N = N \ll 1 \)임을 생각해보면 결국 연속된 1, 즉 "11"이 존재하지 않아야 한다는 것을 의미합니다.

 

2. \( 1 \) 이상 \( N \) 이하의 수에서 [1]을 만족시키는 수의 개수는?

어떤 수 \( x \)가 [1]을 만족시키려면, 아래 두 경우 중 하나여야 합니다.

• \( x \gg 1 \)이 [1]을 만족시키는 경우
• \( x \& 3 \)이 "11"인 경우

// 그냥 "11"이 마지막 비트에서 나오는지 / 아닌지 나눈 겁니다.

 

이제, 이를 토대로 아래 함수를 정의해봅시다.

\( f(x, d) \) = \( 1 \) 이상 \( x \) 이하의 수 중, [1]의 조건을 만족하면서 마지막 비트가 \( d \)인 수의 개수

 

이 함수의 값을 알고 있으면, \( f(x) = f(x, 0) + f(x, 1) \)로 문제의 답을 알아낼 수 있습니다.

// 실제 문제는 여기서 \( f(R) - f(L-1) \)로 풀 수 있겠죠.

 

이제, 마지막 비트를 고려해가면서 아래 방식으로 문제를 풀 수 있습니다.

// \( g(x) \) = \( x \)가 [1]의 조건을 만족하는가? (Boolean)

• \( N \)이 짝수라면, \( N \)을 따로 처리해줍니다.
  \( f(N, 0) = f(N-1, 0) + g(N) \), \( f(N, 1) = f(N-1, 1) \)
  // \( N \)이 짝수이기 때문에, 이 결과값이 \( f(N, 0) \)에 더해지겠죠.
  // \( 1 \)부터 \( N-1 \)까지는 그냥 \( f(N-1, *) \)로 구해집니다.
• \( N \)이 홀수라면, 아래와 같이 비트로 나눠서 풀 수 있습니다.
  \( f(N, 0) = f(N \ll 1, 0) + f(N \ll 1, 1) \), \( f(N, 1) = f(N \ll 1, 0) \)
  // 마지막 비트가 0인 건, 이전 비트가 0이든 1이든 상관없지만,
  // 마지막 비트가 1이라면, 이전 비트가 0으로 고정되어야겠죠.
  // \( N \ll 1 \) 부분은 그냥 마지막 비트를 제외하고 생각할 때 만들 수 있는 값들을 의미합니다.

 

3. 코드

bool chk(ll val){
    while (val){ if ((val&3) == 3){ return 0; } val >>= 1; }
    return 1;
}
 
pl2 dnc(ll val){
    if (val == 0){ return {1, 0}; }
    if (~val&1){ pl2 p = dnc(val-1);
        if (chk(val)){ p.fr += 1; }
        return p;
    }
    pl2 p = dnc(val>>1);
    return { p.fr+p.sc, p.fr };
}
 
void Main(){
    int t; cin >> t; while (t--){
        ll st, ed; cin >> st >> ed;
        pl2 p1 = dnc(st-1), p2 = dnc(ed);
        cout << ed-st+1 -p2.fr-p2.sc +p1.fr+p1.sc << endl;
    }
}