Codeforces Round #406 (Div. 2) C. Berzerk

http://codeforces.com/contest/787/problem/C

이 문제는 게임 dp 문제인데 Nim 게임과 같은 게임 dp 문제와 다른점이 하나 있다.

Nim 게임에서는 보통 두 플레이어가 매 턴 마다 돌을 한개 이상씩 가져가기 때문에 돌이 점점 줄어들고, 그렇기 때문에

돌의 개수와 현재 차례인 플레이어, 이 두가지로 하나의 상태를 정의할 때 그래프로 표현해 보면 노드 A에서 노드 B로 가는 경로가

여러개가 있을 수는 있지만 한번 방문한 노드는 다시 방문되어지지 않는다 (즉, 사이클이 없다)

하지만 이 게임에서는 monster 가 움직일 칸 수를 번갈아서 결정하다 보면 게임 판이 원의 형태로 되어있기 때문에 현재 차례인 

플레이어와 현재 monster의 위치가 다시 같은 상태가 돌아올 수도 있기 때문에 마찬가지로 현재 monster의 위치와 턴을 가진 플레이어로

상태를 정의하고 그래프로 나타냈을 때 사이클이 생기게 된다. 사이클이 없을 때보다 있을 때 조금 더 복잡해 지는 이유 중 하나는

사이클이 생기면 게임이 끝나지 않을 수도 있다는 것이다. 잘 생각해 보면 Nim 게임에서는 매 턴마다 플레이어는 돌을 하나 이상 가져가야 

하기 때문에 돌이 계속해서 줄어들고, 그러면 아무리 두 플레이어가 최선의 선택을 한다고 해도 언젠가는 무조건 게임이 끝날 수 밖에 없고

승자와 패자는 반드시 존재하게 된다. 하지만 이런 원형 게임판에서는 monster 의 위치라는 변수가 다시 같은 자리로 돌아올 수 있기 때문에

두 플레이어가 최선의 선택을 한다면 영원히 게임이 끝나지 않을 수도 있는 것이다.

그렇기 때문에 문제에서는 게임판의 크기가 주어지고 각 플레이어가 먼저 시작할 때, 그리고 현재 몬스터의 위치에 따라

이기는지, 지는지, 아니면 영원히 끝나지 않는지 구하는 것을 요구한다.

그렇다면 상태 그래프가 이렇게 사이클이 될 때는 어떻게 구할까?

우선 각각의 상태를 노드로, 그리고 A상태에서 B상태로 전이 가능하다는 것을 엣지로 나타내보자.

일단 일반적인 게임 dp 에서 처럼 다음 노드 중 하나라도 Lose 이면 나는 Win 이며, 모든 다음 노드가 Win 이면 나는 Lose 이다.

그런데 여기서는 Win도 Lose 도 아닌 노드가 있을 수가 있다. 이 때가 바로 Loop 이다.

블랙홀의 위치를 0으로 보고, 하나의 노드를 (지금 차례 플레이어, 몬스터의 위치) 로 표현해보면 처음에 확실히 Lose 인 것은 (0,0)과 (1,0) 이

될 것이다. 위상 정렬에서 노드를 하나씩 끊어나가듯이 처음에 각 노드마다 outdegree를 주고

현재 노드가 Lose 로 확정이 되었으면 이 이전 노드는 무조건 Win으로 확정이 될 것이고 그러면 이 노드부터 재귀호출을 한다. 왜냐하면

결과 노드부터 반대로 따라 가면서 확실히 정해지는 노드들을 모두 정해 준 뒤에 정해지지않은 노드는 Loop이고 정해진 노드는 그 정해진 대로 Win이나 Lose 이기 때문이다.

그리고 만약 현재 노드가 Win 으로 확정이 되었으면 이전 노드의 outdegree 를 1 감소시켜준다. 왜냐하면 다음 노드가 하나라도 Lose가 있다면 현재 노드는 Win 으로 확정이 되고 여기서부터 재귀호출을 하면 되지만 다음노드 중에 Lose가 하나도 없다면 모두 Win이어야 현재 노드의 상태가 (Lose 로)확정이 되기 때문에 다음 노드중에 Win이 몇개 나왔는지를 체크 해주기 위함이고, 만약 다음 노드들이 모두 Win이었다면 모든 다음노드에 대해 확인을 해준 뒤에 outdegree가 0이 되고 나서야 현재 노드의 승패가 Lose로 확정이 되고, 또 그 노드부터 재귀호출이 가능하기때문이다.

그리고 한가지 처리해 주어야 할 예외는 만약 이전 노드가 블랙홀의 위치이면 무시해주고, 이미 상태가 Win이나 Lose로 정해졌어도 무시해준다. (return 으로)

#include <bits/stdc++.h>
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
 
int N;
int cntMv[2];
int moves[2][7003];
int canWin[2][7003];
int inDegree[2][7003];
 
const int LOSE = 1;
const int LOOP = 0;
const int WIN = 2;
const int NOTDET = 3;
 
int trans(int x){
    return x<0 ? x+N : x;
}
void go(int turn, int pos){
    for(int i = 0; i < cntMv[turn^1]; i++){
        int mov = moves[turn^1][i];
        int prev = trans(pos-mov);
        if(prev == 0 || canWin[turn^1][prev] != LOOP) continue;
        if(canWin[turn][pos] == LOSE) {
            canWin[turn^1][prev] = WIN;
            go(turn^1,prev);
        }
        else if(canWin[turn][pos] == WIN){
            inDegree[turn^1][prev]--;
            if(inDegree[turn^1][prev]==0) canWin[turn^1][prev] = LOSE, go(turn^1,prev);
        }
    }
}
int main() {
    fastio();
    cin >> N;
    cin >> cntMv[0];
    for(int i = 0 ; i < cntMv[0]; i++) 
        cin >> moves[0][i];
    
    cin >> cntMv[1];
    for(int i = 0 ; i < cntMv[1]; i++) 
        cin >> moves[1][i];
 
    for(int i = 0; i < 2; i++){
        for(int j = 0 ; j < N; j++){
            inDegree[i][j] = cntMv[i];
        }
    }
 
    canWin[0][0] = canWin[1][0] = LOSE;
    inDegree[0][0] = inDegree[1][0] = 0;
    go(0,0);
    go(1,0);
    
    for(int i = 0 ; i < 2; i++){
        for(int j = 1 ; j < N; j++){
            if(canWin[i][j] == WIN) cout << "Win ";
            else if(canWin[i][j] == LOOP) cout << "Loop ";
            else cout << "Lose ";
 
        }
        cout << "\n";
    }
    return 0;
}