UCPC 은퇴한 자들의 게임 - stonejjun의 game theory 풀이

문제 링크 : https://www.acmicpc.net/problem/22883

의도된 풀이

주최측에서 의도한 풀이는 관찰을 통해서 주어진 임의의 게임판을 1*a 혹은 b*1 게임판으로 바꾸는 것이었다. 그렇게 되면 특정 게임판은 가로로만 이동이 가능하거나, 세로로만 이동이 가능하기 때문에 바로 둘이 각각 최대 몇턴 동안 살아남을 수 있는지가 구해진다. 따라서 직관적으로 누가 이길지를 계산할 수 있다.

 

Stonejjun의 풀이

 Part 1. 기본 지식과 유리도의 이해.

 이 게임은 기본 상태보다 자신이 플레이 한 후의 상태가 자신에게 더 불리해지는 게임이다. 즉, 자신이 선공으로 이기면 후공으로 해도 이기며, 후공으로 지면 선공으로 해도 지고, 자신이 3번 행동을 하고 시작하면 훨씬 불리한 상태로 시작하는 것이다.
 이러한 종류의 게임은 Combinational Game Theory에서는 Temperatue game 종류로 구분되고 그 중에서 행동하면 불리해 지는 게임을 특별히 "Cold Game"으로 분류한다. 이러한 게임의 특징은 각 게임판의 유리도를 모두 더한 뒤 값이 양수면 a 음수면 b 0이면 후공이 이기게 된다는 것이다. 각 게임판의 값을 모두 xor 했던 Sprague - Grundy와는 다른 계산 방식이다. 

※ 이제부터는 가로 쪽, 즉 제연이가 유리할 수록 +, 세로쪽, 덕인이가 유리할 수록 -로 지칭한다
※ 이제부터 지칭하는 모든 게임판은 울타리 내부 부분만을 의미한다. 
※ 지칭하는 울타리의 색깔은 문제 지문에서의 색깔을 따른다.

 위의 의도된 풀이에서는 이러한 지식을 몰라도 유리도가 자연스럽게 나왔지만, 이 지식을 알고 본다면 1*a 게임판은 a-1의 유리도를 가진 게임판이며 b*1 게임판은 -(b-1)의 유리도를 가진 게임판으로 이를 모두 더한 값으로 결정된다는 부분다.
 하지만 오히려 이 지식을 알고 있으면, 어려운 관찰을 통해서 1*a 게임판으로 바꿔서 직관적인 계산을 할 필요 없이 그냥 원래 게임판에서 계산을 하면 된다.

 각 게임판의 유리도를 어떻게 계산할까? 각 게임판의 유리도는 내가 그 게임판에서 얻을 수 있는 추가턴의 수를 의미한다. 

위의 그림을 보자. 1번 게임판은 제연이가 2번의 턴을 추가로 쓸 수 있는 공간이기 때문에 유리도가 +2이다. 2번 게임판은 서로 1번씩 움직이기 때문에 유리도가 0이다. 3번 게임판은 -1처럼 보일 수도 있지만, 제연이는 1칸 움직이는 순간 2의 손해를 보기 때문에 최적의 전략에서 절대로 저 게임판을 건들지 않는다. 따라서 3번 게임판의 유리도는 0이다. 4번 게임판은 덕인이가 한 칸만 움직일 수 있다. 한 칸을 더 움직이는 순간 손해를 보기 때문이다. 따라서 4번 게임판의 유리도는 -1이다. 5번 판에서는 둘 다 한 칸씩 움직인다. 이때 덕인이가 추가로 한 칸 움직이는 것은 제연이도 한 칸을 추가로 이동할 수 있게 만들기 때문에 

 Part 2. 게임판에서 유리도를 구하는 방법

이제부터 울타리 두 직선을 묶어서 한 세트로 보려고 한다. 말이 굉장히 이상한데, 입력을 말하자면 파란색 울타리에서 연속된 R의 개수와 연속된 D의 개수를 묶어서 생각하고, 빨간색 울타리에서 연속된 D의 개수와 연속된 R의 개수를 묶어서 생각할 것이다. 위의 5개 게임판으로 예시를 들어보려고 한다.

1번 게임판 : 파란색 울타리 (R: 3, D: 1), 빨간색 울타리 (R: 3, D: 1)
2번 게임판 : 파란색 울타리 (R: 2, D: 2), 빨간색 울타리 (R: 2, D: 2)
3번 게임판 : 파란색 울타리 (R: 2, D: 3), 빨간색 울타리 (R: 1, D: 1) , (R: 1, D: 2)
4번 게임판 : 파란색 울타리 (R: 1, D: 2), (R: 2, D: 1) 빨간색 울타리 (R: 3, D: 3)
5번 게임판 : 파란색 울타리 (R: 2, D: 2), (R: 1, D: 1) 빨간색 울타리 (R: 3, D: 3)

 여기서 5번 게임판을 볼 것이다. 맨처음 말이 (1,1)각각의 첫번째 묶음을 보면 파란색 울타리는 (2,2) 이고, 빨간색 울타리는 (3,3) 이다. 
 파란색 울타리의 R은 2인데, 빨간색 울타리의 R은 3이다. 따라서 제연이 입장에서는 최대한 오른쪽으로 움직이는 것이 이득이다. 빨간색 울타리의 R이 더 크기 때문에 3번 게임판 처럼 오른쪽으로 갔다가 손해볼 일이 없다. 3번 게임판에서는 파란색 울타리의 R이 더 큰 것과 대조되는 부분이다.
 당연히 덕인이는 하고 싶은대로 아래로 갈 수 없다. 왜냐하면 빨간색 울타리의 D가 파란색 울타리의 D보다 크기 때문이다. 파란색 울타리의 다음 세트 (1,1) 을 모르는 상태에서 일단은 마음대로 아래로 움직일 수 없으며, 파란색 울타리의 D가 2이기 때문에 1칸까지 아래로 움직이는 것이 자유이다.

 수치적으로 정리를 해보자. 조건별로 나누지 않고, 묶어서 정리하면 min(파랑R,빨강R) -1 만큼 오른쪽으로 이동할 수 있고, min(파랑D,빨강D) -1 만큼 아래쪽으로 이동할 수 있다. 

 위와 같은 방식으로 5번 게임판에서는 일단 2,2 까지 이동할 것을 알 수 있다. 여기서 우리는 추가적인 관찰을 해야한다. 이 시점에서 저 게임판의 주도권은 덕인이에게 있다. 덕인이가 행동을 하지 않는다면 저 게임판의 추가 값은 0으로 끝난다. 
 만약 덕인이가 한 칸 내렸다고 가정을 해보자.(위치는 3,2) 그 시점에서부터 유리도를 계산하여 1보다 크면 덕인이는 절대 내리지 않을 것이며, 2,2 시점에서 끝난다. 1이면 의미가 없다. 만약 0 이하라면 덕인이는 무조건 한 칸을 내릴 것이며, 전체 게임판의 유리도는 -1+(3,2에서 부터 계산한 유리도) 가 될 것이다. 

예시로 위의 그림을 생각해보자. 2,2 시점까지는 유리도가 0이다.
5-1 번 게임판에서 (3,2)로 시작하면 유리도가 1이기 때문에 5-1 게임판의 총 유리도는 min(0,-1+1)=0이다. 
5-2 번 게임판에서 (3,2)로 시작하면 유리도가 2이기 때문에 5-2 게임판의 총 유리도는 min(0,-1+2)=0이다.
5-3 번 게임판에서 (3,2)로 시작하면 유리도가 0이기 때문에 5-3 게임판의 총 유리도는 min(0,-1+0)=-1이다.

이렇게 계산 과정이 재귀적으로 일어나게 된다. 일단 한 번 멈추는 위치까지의 유리도 계산, 그 위치에서 행동을 할 수 있는 주도권에 대한 계산, 주도권에 따라서 min,max로 제한을 시켜놓고 그 이후에 더 행동이 될 지에 대한 추가적인 계산의 시작. 이렇게 재귀적으로 반복이 되게 된다. 그러다가 결국 빨간 울타리의 묶음과 파란 울타리의 묶음이 동일하면, 이는 마지막에 도착하여 직사각형 모양이라는 것이고, 재귀 값을 그대로 돌려주면 된다.

이렇게 각 판의 유리도를 구하고 다 더해서 0과 비교하는 것으로 누가 이길지 예측할 수 있다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> piii;
#define ff first
#define ss second
#define ep emplace_back
#define eb emplace
#define pb push_back
#define all(v) v.begin(), v.end()
 
vector<pii> v1;
vector<pii> v2;
ll ans=0;
 
inline ll sol(ll x,ll y){
    ll fl1=x;
    ll fl2=y;
    ll ret=0;
 
    auto k1=v1[x];
    auto k2=v2[y];
    if(k1==k2) return k1.ff-k1.ss;
 
    ll a=min(k1.ff,k2.ff)-1;
    ll b=min(k1.ss,k2.ss)-1;
    ret+=a-b;
    k1.ff-=a;
    k2.ff-=a;
    k1.ss-=b;
    k2.ss-=b;
 
    if(k1.ff==1){
        k2.ss--;
 
        v1[x]=k1;
        v2[y]=k2;
 
        x++;
        v1[x].ff++;
 
        ll vall=sol(x,y);
        return ret+min(0LL,-1+vall);
    }
 
    if(k2.ss==1){
        k1.ff--;
        v1[x]=k1;
        v2[y]=k2;
        y++;
        v2[y].ss++;
        ll vall=sol(x,y);
        return ret+max(0LL,1+vall);
    }
 
    ll xx11=k1.ff;
    ll xx22=k2.ss;
 
    x++;
    y++;
    v2[y].ss+=k2.ss-1;
    v1[x].ff+=k1.ff-1;
 
    ll vall=sol(x,y);
    if(vall>k1.ff-1) vall=k1.ff-1;
    if(vall<-(k2.ss-1)) vall=-(k2.ss-1);
    return ret+vall;
}
 
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    ll i,j,k,l,m,n,kk;
    cin>>k;
 
    for(kk=1;kk<=k;kk++){
        v1.clear();
        v2.clear();
 
        cin>>n>>m;
        string s1,s2;
        cin>>s1>>s2;
        if(s1[0]=='D') swap(s1,s2);
 
        n+=m;
        ll val1=0,val2=0,fl=0;
        for(i=0;i<n;i++){
            if(i==0){
                val1++;
                continue;
            }
            if(s1[i]=='R'){
                if(s1[i-1]=='D'){
                    v1.pb({val1,val2});
                    val1=val2=0;
                }
                val1++;
            }
            else{
                val2++;
            }
        }
        v1.pb({val1,val2});
 
        val1=0,val2=0,fl=0;
        for(i=0;i<n;i++){
            if(i==0){
                val2++;
                continue;
            }
            if(s2[i]=='R'){
                val1++;
            }
            else{
                if(s2[i-1]=='R'){
                    v2.pb({val1,val2});
                    val1=val2=0;
                }
                val2++;
            }
        }
        v2.pb({val1,val2});
        ans+=sol(0,0);
    }
 
    if(ans<=0) cout<<"Second";
    else cout<<"First";
}