BOJ 13409 - Black and White Boxes

문제 태그 : https://www.acmicpc.net/problem/13409

※ 내가 관찰로 푼 문제들 중 하나이다. 따라서 갑자기 생각난 아이디어와 노가다, 말도 안되는 관찰들로 풀이가 이루어 질 예정이다.
※ Blackking과 함께 풀었다.

문제 소개

N개의 상자 그룹이 있다. 각 상자그룹은 A박스와 B박스가 쌓여있는 형태이다. 이 중 몇 그룹을 사용해서 게임을 진행할 것이다. 돌아가면서 A는 A박스와 그 위에 쌓인 박스 모두를 제거하고, B는 B박스와 그 위에 쌓인 모든 박스를 제거한다. 이렇게 진행하며 더이상 할 행동이 없는 사람이 지게 된다. 이때 공정한 게임이 될 수 있는 최대 박스의 갯수를 구하시오. (단, 공정한 게임은 먼저 하는 사람에 따라 승패가 바뀌는 게임이다.)

사고의 흐름

Blackking과 함께 2일 동안 밤새서 이 문제에 대해 이야기했다. 관찰할 수 있는 다양한 사실이나 아이디어에 대해 생각날 때 마다 끊임 없이 Brain Storming 하는 방식으로 진행했다. 2일 정도 지나니까 뭔가 연관성이 생기고 실마리가 보이는 것 같아서 지금까지 Brain Storming한 내용들을 정리하였고, 그 내용을 바탕으로 토론을 해서 문제를 풀었다. 

일단 가장 먼저 가장 아랫 층에 상자가 몇 개 있는지가 중요하다고 생각을 했다. 그 중 가장 위의 상자를 들어내고, 그 이후의 상자는 자신이 원할때 자유롭게 한 번씩 턴을 넘길 수 있기 때문이다. 
그래서 최선의 플레이는 '자신의 가장 아래의 연속된 상자 무더기 중 가장 위의 상자를 선택한다'인 줄 알았지만, 반례가 존재했다. 그냥 자신의 가장 윗상자를 선택하는 것이 이득이었다. 
하지만 위에 상자가 아무리 많아도 아래 상자가 중요하다는 것은 맞는 것 같았다.

숫자로 변환하는 방법에 대해서 예기 해봤다. 그런디와 같은 느낌으로 해결할 수 있을 것 같았다. 위에 상자가 아무리 많아도 아래 상자가 중요하기 때문에 이진수에 관한 이야기도 나오게 되었다. 
이와 별개로 0이라는 숫자가 공정한 게임과 관련있을 것 같다는 의견이 나왓다.

갑자기 Blackking이 등가 무더기에 대해 의견을 제시했다. 즉 BW+ BW = B와 같이 바꿀 수 있다는 것이었다. 그렇다면 B=-W 라고 볼 수 있는지도 궁금했고, BWW에 대해서도 물어봤다. 계속 끄적여본 결과
BWW+BWW=BW , BWW+BWW+BW=B 와 같은 식들이 나올 수 있었다.
따라서 BWWW*8=BWW*4=BW*2=B 와 같은 식이 나오게 되었고, 이진법에 더욱 합리적 의심을 가할 수 있었다.

집합적 관점으로 보았을 때 박스 집합 s 가 무승부 박스 집합t 가 무승부면 박스 집합 s+t 는 무승부다. 또한 박스 집합 s 가 무승부 박스 집합t 가 무승부면 박스 집합 s-t도 무승부다. 따라서 등가교환, 숫자를 더하거나 XOR을 취해서 0이면 공정하다는 주장에 힘이 실렸다. 

위치에 집중을 했다. 같은 위치에 B랑 W를 놔도 평행은 안깨지고, 다른 위치에 놓는 순간 깨진다. 위에서 BWWW*8=BWW*4=BW*2=B의 식을 생각해 보면 각 값을 B를 기준으로 바꿀 수 있다고 생각했다. 
BB=2B BBW=1.5B의 식이 나오면서 1:1:1:1:1:0.5:0.25:0.125의 점수배치가 정확히 맞아 떨어지게 되었다. 이런식으로 점수를 분배해서 0이되게 하는 묶음을 찾으면 되겠다는 생각을 하게되었다. 

Meet in the Middle기법을 사용하면 $20*{2^{20}}$ 의 시간복잡도를 가지게 되고, 시간안에 작동할 수 있을 것 처럼 보였다. 바로 코드를 짜기 시작했고, 바로 맞았다. 

BWWW*8=BWW*4=BW*2=B 이 식을 찾게 된게 그냥 너무 주요했다고 생각했다. 이 식에다가 숫자로 바꾸자는 생각을 해보니 BWWW=0.125B와 같은 매칭이 생기게 되고, 이진법이 절묘하게 스며들어가서 풀이의 조각들이 맞춰졌던 것 같다. 진짜 팀 대회같은 느낌으로 문제를 풀었다. 물론 2일을 거의 밤새긴 했지만 말이다. 

+@
 만약 이와 관련된 사전지식을 공부하고 싶다면 game theory 의 hackenbush 혹은 red - blue hackenbush 관련 내용입니다.

코드

※ 오래 고민해 보지 않고 문제 수, 경험치만을 위해서 코드를 복붙하는 등의 행위는 큰 페널티를 받을 수 있습니다.

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
#define ff first 
#define ss second 
 
pii arr1[3010101];
pii arr2[3010101];
ll arr[40];
ll asz[40];
ll brr[40];
ll bsz[40];
 
string s;
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    ll i,j,k,l,m,n;
    cin>>n;
    ll n1=n/2;
    ll n2=n-n1;
    for(i=0;i<n1;i++){
        cin>>s;
        ll mul=1LL<<40;
        ll chk=1;
        for(j=0;j<s.size();j++){
            if(j&&s[j]!=s[j-1]) chk=0;
            if(chk==0) mul/=2;
            if(s[j]=='B') arr[i]+=mul;
            else arr[i]-=mul;
        }
        asz[i]=s.size();
    }
    for(i=0;i<n2;i++){
        cin>>s;
        ll mul=1LL<<40;
        ll chk=1;
        for(j=0;j<s.size();j++){
            if(j&&s[j]!=s[j-1]) chk=0;
            if(chk==0) mul/=2;
            if(s[j]=='B') brr[i]+=mul;
            else brr[i]-=mul;
        }
        bsz[i]=s.size();
    }
    ll bn1=(1LL<<n1);
    ll bn2=(1LL<<n2);
 
    for(i=1;i<=bn1;i++){
        ll now=0;
        ll now2=0;
        for(j=0;j<n1;j++) 
            if((1LL<<j)&i){
                now+=arr[j];    
                now2+=asz[j];
            }
        arr1[i]={now,now2};
    }
    for(i=1;i<=bn2;i++){
        ll now=0;
        ll now2=0;
        for(j=0;j<n2;j++) 
            if((1LL<<j)&i){
                now+=brr[j];
                now2+=bsz[j];    
            }
        arr2[i]={now,now2};
    }
    sort(arr1+1,arr1+1+bn1);
    sort(arr2+1,arr2+1+bn2);
    ll ans=0;
    for(i=1;i<=bn1;i++){
        if(i!=bn1&&arr1[i].ff==arr1[i+1].ff) continue;
        pii k={-arr1[i].ff+1,-1e18};
        ll idx=lower_bound(arr2+1,arr2+1+bn2,k)-arr2-1;
        if((arr1[i].ff+arr2[idx].ff)==0) ans=max(ans,arr1[i].ss+arr2[idx].ss);
    }
    cout<<ans;
}