Independent Nim

문제

• 난이도: 1112

• 링크: Independent Nim

풀이

먼저 게임의 이기는 상태와 지는 상태를 정의하겠습니다. 어떤 게임의 상태가 주어졌을 때, 현재 턴에 최선을 다했을 때 이길 수 있다면 이기는 상태, 아니면 지는 상태라고 합시다. 예를 들어 상태 1 1 0 1은 지는 상태입니다.

$A_i$중 연속된 $1$을 하나의 게임으로 생각하고, 전체 게임을 여러 개의 게임을 병렬로 진행하는 것으로 생각합시다. 한 번의 조작에서 인접하지 않은 여러 원소를 고를 수 있으므로, 여러 게임을 동시에 조작할 수 있습니다.

예를 들어 예제의 세 번째 테스트케이스는 $N = 3$, $N = 4$, $N = 5$인 게임을 병렬로 진행하는 것으로 생각할 수 있습니다.

만약 병렬로 진행되는 게임 중 이기는 상태인 게임이 하나라도 있다면, 각 이기는 게임을 지는 상태로 만드는 조작을 동시에 수행할 수 있습니다. 그러면 후공의 턴에 모든 게임이 지는 상태가 됩니다.

이때 후공은 어떤 행동을 하더라도 하나 이상의 게임이 이기는 상태로 변하므로 선공이 다시 모두 지는 상태로 바꿀 수 있습니다.

따라서 이 문제는 병렬로 진행되는 게임 중 이기는 상태인 것이 하나라도 있는지 판별하는 문제로 바꿔서 해결할 수 있고, 모든 $A_i$가 $1$인 경우만 해결하면 문제를 풀 수 있습니다.

$N = 1$인 경우 이기는 상태, $2$인 경우 지는 상태입니다. $N \ge 3$에 대해서는 다음 방법으로 이길 수 있습니다.

1. $3$으로 나눈 나머지가 $1$인 경우
   첫 번째부터 시작해서 $1, 4, 7, 10, \dots$번째 원소를 $0$으로 만듭니다.
2. $3$으로 나눈 나머지가 $2$인 경우
   세 번째부터 시작해서 $3, 6, 9, 12, \dots$번째 원소를 $0$으로 만듭니다.
3. $3$으로 나눈 나머지가 $0$인 경우
   위 두 가지 방법 중 아무거나 사용합니다.

이렇게 하면 전체 게임이 $N = 2$인 게임들로만 나눠지므로 후공의 턴이 되었을 때 모든 게임이 지는 상태가 됩니다.

따라서 $N = 2$를 제외하고 모두 이기는 상태입니다.

$1$이 연속되는 부분의 길이를 세어서 $2$가 아닌 것이 하나라도 존재하는지 체크하면 각 테스트케이스를 $O(N)$에 해결할 수 있습니다.

코드

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int N;
    cin >> N;
 
    bool winExists = false;
    int sz = 0;
    for (int i = 1; i <= N; i++) {
        int A;
        cin >> A;
 
        if (A == 0) {
            if (sz > 0 and sz != 2) winExists = true;
            sz = 0;
        } else sz++;
    }
    if (sz > 0 and sz != 2) winExists = true;
 
    cout << (winExists ? "Alice" : "Bob") << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
 
    while (t--) solve();
 
    return 0;
}