[BOJ 22851] 흑왕과 어둠의 게임 대진표

체감 난이도: Diamond IV + 0.37

태그

• Case Work (많은 조건 분기)
• Ad Hoc (애드 혹)

 

풀이

1. 1번의 대전 (1 vs 1)에서 얻을 수 있는 정보는?

$a$와 $b$가 (이 순서대로) 대결을 했다면,

• $a$가 이김: $a$의 패가 $b$의 패를 이기거나 비김
• $b$가 이김: $b$의 패가 $a$의 패를 이김

이라는 정보를 얻을 수 있습니다.

 

지금부터는, 편의상 아래와 같은 Notation을 놓겠습니다.

$a^{+},a^0,a^{-}$: 각각 $a$를 이기는 패, $a$과 비기는 패, $a$한테 지는 패 를 의미합니다.

$a\ge b,a<b$: $a,b$ 순서대로 대결했을 때, 각각 $a$가 이김과 $b$가 이김을 의미합니다.

 

가위바위보의 특성상, ${\left(a^{+}\right)}^{+}=a^{-}$, ${\left(a^{-}\right)}^{-}=a^{+}$, $a^0=a$입니다.

 

2. 특정한 사람이 이길 수 있는 대진표를 짤 수 있게 되는 조건은?

$K$번째 사람의 패를 그냥 $k$라고 해봅시다.

 

어차피 우리가 원하는 대로 재배치를 할 것이므로, $k^{-},k^0,k^{+}$의 개수만 알고 있으면 됩니다.

 

그런데, $k$의 입장에서 걱정해야 하는 건 $k^{+}$ 뿐입니다.

그리고 이 $k^{+}$를 확실히 제거하기 위해서는 $k^{-}$가 필요하죠.

 

이제, 하나씩 생각해봅시다.

 

2-1. 참가자가 4명이라면?

• $k^{+}$가 0명이라면, 자명히 가능합니다.
• $k^{+}$가 1명이라면, $k^{-}$ 1명으로 처리할 수 있습니다.
• $k^{+}$가 2명 이상이라면, 처리가 불가능합니다.

 

2-2. 참가자가 8명이라면?

• $k^{+}$가 0명이라면, 자명히 가능합니다.
• $k^{+}$가 3명 이하라면, $k^{-}$ 1명으로 처리할 수 있습니다.
  • + 3명과 - 1명을 오른쪽의 4칸에 넣으면, 그 곳의 승자는 - 1명이 되겠죠.
• $k^{+}$가 4명이라면, 3명을 $k^{-}$ 1명으로, 나머지 1명을 $k^{-}$ 1명으로, 총 2명으로 처리할 수 있습니다.
  • [ [k ?], [+ -] ], [ [+ +], [+ -] ]으로 배치하면 됩니다.
• $k^{+}$가 5명 이상이라면, 처리가 불가능합니다.

 

2-3. 일반화를 해보면?

참가자가 $2^m$명이라면,

• $k^{+}$가 0명이라면, 자명히 가능합니다.
• $k^{+}$가 $2^{m-1}-1$명 이하라면, $k^{-}$ 1명으로 처리할 수 있습니다.
  • $2^{m-1}-1$명의 $k^{+}$과 1명의 $k^{-}$을 $2^{m-1}$ 크기의 왼쪽 대진표에 넣으면 됩니다.
• $k^{+}$가 $2^{m-1}-1$명 초과라면, $k^{-}$ 1명으로 $2^{m-1}-1$명의 $k^{+}$을 처리한 뒤,
  나머지는 $2^{m-1}$ 크기의 대진표로 재귀적으로 처리합니다.
  • $2^{m-1}-1$명의 $k^{+}$을 처리하는 건 위와 동일하게, 왼쪽 대진표에 몰아넣으면 됩니다.
  • 재귀적으로 처리하는 건 오른쪽 대진표가 되겠죠.
  • 재귀적으로 처리하므로, 종료 조건이 있어야겠죠. 이는 위에서 계산한 (2-1)을 사용하면 됩니다.

 

3. 알고 있는 정보를 최대한 활용해보자.

사실 이 시점에서 활용할 정보는 많지 않습니다.

애초에 쿼리에 대해 생각도 해보지 않았는걸요.

 

하지만, 그래도 기초적인 정보 몇 개는 알고 있습니다.

• $k$가 가지고 있는 패는 자명히 $k^0$입니다.
• $k^{+},k^0,k^{-}$의 개수만 세면 되므로, 인덱스를 크게 신경쓰지 않아도 됩니다.

 

4. 패를 알고 있는 사람을 토대로, 새로운 사람의 패를 알아내보자.

기본적인 방법으로는, $k^0$와 $a$를 대전하게 한 뒤 $a$와 $k^0$를 대전하게 하는 방식이 있습니다.

이렇게 하면, 2번의 쿼리로 1명의 패를 알아낼 수 있겠네요.

 

하지만 사람 수 (65536명)를 고려하면, 쿼리 제한 (44444회)을 훨씬 넘어서게 됩니다.

 

5. 패를 알고 있는 사람들 ($k^0,k^{+}$)을 토대로, 새로운 사람들의 패를 알아내보자.

만약 우리가 $k^0$과 $k^{+}$인 사람을 각각 1명씩 알고 있었다고 해봅시다.

이를 토대로, 새로운 사람 $a$와 $b$의 패를 알아낼 수 있을까요?

 

처음으로 드는 생각은 $k^0$과 $k^{+}$을 분리해야 한다는 것입니다.

그럼, $k^0,a,k^{+},b$로 쿼리를 날려볼까요?

 

아쉽게도 위 쿼리로는 모든 경우를 알아낼 수 없습니다.

만약 $k^0\ge a$고 $k^{+}\ge b$라는 결과가 나오면, $a$와 $b$로 가능한 경우가 총 2×2 = 4가지가 나오게 되고, 이는 $a$와 $b$의 대전 결과 (2가지 output)만으로는 완전히 나눌 수 없기 때문입니다.

 

그럼 역시 쿼리 1번에 패를 알아내는 건 무리일까요?

그렇지는 않습니다.

 

위에서 발생한 문제는 $a$와 $b$가 만날 때, 둘 다 2가지씩의 경우를 가지고 있다는 점이었습니다.

그럼, 순서를 적당히 바꿔서, 둘이 만날 때 한 쪽은 1가지의 경우만을 가지게 할 수 있을까요?

 

가능합니다. $b$와 $k^{+}$의 순서를 바꾸면, $b$와 $k^{+}$가 비길 때 올라가게 되는 사람이 달라지므로,

원래 만났어야 하는 2가지 경우는 만나지 않게 되고, 대신 1가지 경우에서 만나게 되겠죠.

 

실제로, $k^0,a,b,k^{+}$ 순서의 쿼리를 날리게 되면, 아래 4가지 경우로 문제를 풀 수 있습니다.

• $k^0\ge a$, $b\ge k^{+}$ → $k^0\text{ vs }b$, $a\text{ vs }{k}^{+}$
  • $a$로 가능한 경우는 $k^0,k^{-}$이고, 이는 $a\text{ vs }{k}^{+}$에서 유일하게 정해집니다.
  • $b$로 가능한 경우는 $k^{+},k^{-}$이고, 이는 $k^0\text{ vs }b$에서 유일하게 정해집니다.
• $k^0\ge a$, $b<k^{+}$ → $k^0\text{ vs }{k}^{+}$, $a\text{ vs }b$
  • $a$로 가능한 경우는 $k^0,k^{-}$이고, $b$로 가능한 경우는 $k^0$입니다.
  • 이는 $a\text{ vs }b$에서 유일하게 정해집니다.
• $k^0<a$, $b\ge k^{+}$ → $a\text{ vs }b$, $k^0\text{ vs }{k}^{+}$
  • $a$로 가능한 경우는 $k^{+}$이고, $b$로 가능한 경우는 $k^{+},k^{-}$입니다.
  • 이는 $a\text{ vs }b$에서 유일하게 정해집니다.
• $k^0<a$, $b<k^{+}$ → $a\text{ vs }{k}^{+}$, $k^0\text{ vs }b$
  • $a$로 가능한 경우는 $k^{+}$이고, $b$로 가능한 경우는 $k^0$입니다.
  • 이미 유일하니까, 추가 정보는 필요 없겠네요.

 

6. 패를 알고 있는 사람들 ($k^0,k^0$)을 토대로, 새로운 사람들의 패를 알아내보자...?

사실 불가능합니다.

 

$a,b$를 처음에 싸우게 시키면, $a\ge b$는 6가지 경우가 나오게 됩니다.

이는 나중에 나오는 4가지 경우만으로는 분리해낼 수 없겠죠.

 

그럼, $k^0,a,k^0,b$밖에 없는 것 같은데...

이건 (5번)과 동일한 문제점 ($a$와 $b$가 만나면 4가지 경우가 생기지만, 이 시점에서 나눌 수 있는 분기는 2가지)이 나타나므로 불가능합니다.

 

(5번)과 동일한 해결책을 넣으면 되지 않을까요?

아쉽게도...

• $k^0,a,b,k^0$의 쿼리를 날린다면:
  
  • $k^0<a$, $b\ge k^0$ → $a\text{ vs }b$, $k^0\text{ vs }{k}^0$
    • $a$로 가능한 경우는 $k^{+}$이고, $b$로 가능한 경우는 $k^0,k^{+}$입니다.
    • 두 경우 모두 $a\text{ vs }b$에서 $a$가 승리한다는 결과가 나오므로, 구분할 수 없습니다.
• $a,k^0,k^0,b$의 쿼리를 날린다면:
  • $a\ge k^0$, $k^0\ge b$ → $a\text{ vs }{k}^0$, $k^0\text{ vs }b$
    • $a$로 가능한 경우는 $k^0,k^{+}$입니다.
    • 하지만 $a\text{ vs }{k}^0$의 결과는 $a\ge k^0$만 가능하므로, 구분할 수 없습니다.

 

7. 굳이 쿼리 1번에 맞춰야 하나?

(6번)을 보아할 때, 쿼리 1번에 맞추는 건 아무래도 무리가 있는 것 같아보입니다.

극단적으로, 모든 사람의 패가 동일하다면 (5번) 케이스로 넘어가지 못할 것이고,

굳이 그렇지 않다고 해도 $k^{+}$의 수가 적으면, 그걸 찾는 데에도 오래 걸릴테니까요.

 

그런데, 그럼 어떤 전략을 세워야 할까요?

혹시, 쿼리 2번이면 될까요?

 

이론적으로는, 쿼리 2번에 3명의 패를 알아낸다면, 65536/3 × 2 = 약 43690회의 쿼리를 사용하게 됩니다.

제한 내에 들어오긴 하는데... 실제로 할 수 있을까요? (Spoiler: 가능합니다.)

 

8. 패를 알고 있는 사람 ($k^0$)을 토대로, 다른 사람들의 패를 쿼리 2번만에 알아내보자.

저희가 알고 있는 사람의 패는 $k^0$이고, 나머지 3명의 패는 $a,b,c$라고 해봅시다.

 

당연히 첫 번째 쿼리로 많은 걸 알기는 힘들테니, 일단 아무거나 날려볼까요?

$k^0,a,b,c$의 쿼리를 날리면, 아래와 같은 결과를 만날 수 있습니다.

• $k^0<a$
  • $a$로 가능한 경우가 $k^{+}$밖에 존재하지 않습니다.
  • 아직 쿼리 1번이 남았는데... 어라?
  • 우리가 (5번)에서 구한 것과 동일한 상황이 되었습니다!
  • $k^0,k^{+},b,c$를 토대로 (5번)을 적용해주면 됩니다.
• $k^0\ge a$, $b\ge c$ → $k^0\text{ vs }b$, $a\text{ vs }c$
  • $k^0<b$: 위의 $k^0<a$와 비슷하게, $b=k^{+}$이고, 남은 건 (5번)으로 풀어주면 됩니다.
  • $k^0\ge b$: 밑에서 처리해봅시다.
• $k^0\ge a$, $b<c$ → $k^0\text{ vs }c$, $a\text{ vs }b$
  • $k^0<c$: $c=k^{+}$이고, 남은 건 (5번)으로 풀어주면 됩니다.
  • $k^0\ge c$: 밑에서 처리해봅시다.

 

어라? 생각보다 많은 경우가 (5번)으로 처리되었습니다!

좋은 징조 같으니, 좀 더 깊이 가봅시다.

 

지금까지 처리하지 못한 경우는, 아래 4가지 경우입니다.

• $k^0\ge a$, $b\ge c$, $k^0\ge b$, $a\ge c$ → $k^0,b,a,c$
• $k^0\ge a$, $b\ge c$, $k^0\ge b$, $a<c$ → $k^0,b,c,a$
• $k^0\ge a$, $b<c$, $k^0\ge c$, $a\ge b$ → $k^0,c,a,b$
• $k^0\ge a$, $b<c$, $k^0\ge c$, $a<b$ → $k^0,c,b,a$

4가지 경우의 공통점은, $k^0\ge x$가 2개씩 존재한다는 것입니다.

그럼, 이 $x$를 기준으로 묶어봅시다.

• $x=a,b$ → $k^0,b,a,c$, $k^0,b,c,a$
• $x=a,c$ → $k^0,c,a,b$, $k^0,c,b,a$

두 경우의 차이는 그저 b와 c가 swap되었다는 것일 뿐이네요.

그럼, $x=a,c$인 경우는 swap(b, c)를 해준 뒤 $x=a,b$로 처리해주면 될 것 같아보입니다.

 

그럼 이제 $x=a,b$로 고정되었고, $a$와 $b$는 $k^0$이거나 $k^{-}$여야 합니다.

$c$는, $a$와의 대결 결과에 따라 $a\ge c$ ($c=a^0,a^{-}$)거나 $a<c$ ($a^{+}$)겠죠.

 

그럼, 여기서 $c$를 기준으로 케이스를 나눠봅시다.

 

8-1. 8-2와 8-3에서 자주 쓰이는 중요한 사실들

• $k^0\text{ or }{k}^{-}$인 두 사람 $a,b$의 결과가 $a<b$라면, $a=k^{-}$이고 $b=k^0$입니다.
• $k^0\text{ or }{k}^{-}$인 사람 $a$는, $a\text{ vs }{k}^0$을 사용해 $a$의 패를 알아낼 수 있습니다.

 

8-2. 패를 알고 있는 사람 $k^0$과, 패를 대강 알고 있는 두 사람 $a,b$ ($k^0\text{ or }{k}^{-}$), 그리고 $a$와 싸워서 이긴 사람 $c$ ($a^{+}$)

사실 이 경우는, $c$에 대한 정보를 더 알아낼 수 있습니다.

$c=a^{+}={\left(k^0\right)}^{+}\text{ or }{\left(k^{-}\right)}^{+}=k^{+}\text{ or }{k}^0$

 

이번에는 $a$와 $b$끼리 싸우게 해봅시다.

그럼 쿼리는 $a,b,k^0,c$로 날려볼까요?

 

이의 결과는 아래로 나눠볼 수 있습니다.

• $a<b$
  • (8-1번)에서 다룬 바와 같이, $a$와 $b$가 고정됩니다.
  • 추가적으로, $c$는 $a$에 대해 고정되어있으므로, $c$까지 알 수 있겠네요.
• $a\ge b$, $k^0\ge c$ → $a\text{ vs }{k}^0$, $b\text{ vs }c$
  • 우선, $c$로 가능한 경우가 $k^0$으로 고정됩니다.
  • 그럼 $a$ 역시 한 가지로 고정되고, $b$는 $b\text{ vs }(c=k^0)$에서 고정됩니다.
• $a\ge b$, $k^0<c$ → $a\text{ vs }c$, $b\text{ vs }{k}^0$
  • $c$로 가능한 경우가 $k^{+}$로 고정됩니다. 그럼 $a$ 역시 한 가지로 고정되겠죠.
  • $b$는 $b\text{ vs }{k}^0$에서 고정됩니다.

 

모든 경우가 성공적으로 구분되었으니, 다음으로 넘어가봅시다.

 

8-3. 패를 알고 있는 사람 $k^0$과, 패를 대강 알고 있는 두 사람 $a,b$ ($k^0\text{ or }{k}^{-}$), 그리고 $a$와 싸워서 진 사람 $c$ ($a^0\text{ or }{a}^{-}$)

$c$의 결과를 고정시키는 게 편할 거 같으니, $a$와 $c$를 붙여봅시다.

그럼 자연스럽게 $b$는 $k^0$와 붙게 되고, (8-1번)에 의해 자명히 한 가지 경우로 고정됩니다.

 

이번에 날리는 쿼리는 $c,a,b,k^0$입니다.

• $c\ge a$, $b\ge k^0$ → $c\text{ vs }b$, $a\text{ vs }{k}^0$
  • $c$는 $a^0$여야 합니다.
  • $b$는 $k^0$이고, $a$는 $a\text{ vs }{k}^0$에 의해 결정됩니다.
• $c\ge a$, $b<k^0$ → $c\text{ vs }{k}^0$, $a\text{ vs }b$
  • $c$는 $a^0$여야 합니다.
  • $b$는 $k^{-}$이고, $a$는 $(c=a^0)\text{ vs }{k}^0$에 의해 결정됩니다.
• $c<a$, $b\ge k^0$ → $a\text{ vs }b$, $c\text{ vs }{k}^0$
  • $c$는 $a^{-}$여야 합니다.
  • $b$는 $k^0$이고, $a$는 $a\text{ vs }(b=k^0)$에 의해 결정됩니다.
• $c<a$, $b<k^0$ → $a\text{ vs }{k}^0$, $c\text{ vs }b$
  • $c$는 $a^{-}$여야 합니다.
  • $b$는 $k^{-}$이고, $a$는 $a\text{ vs }{k}^0$에 의해 결정됩니다.

 

이 경우도 완벽하네요.

 

코드

ai4 ask(int a, int b, int c, int d){
    cout << "? " << a << ' ' << b << ' ' << c << ' ' << d << endl << flush;
    int w, x, y, z; cin >> w >> x >> y >> z;
    array<int, 4> res;
    res[0] = (a==w ? 1 : a==x ? 2 : a==y ? 3 : 4);
    res[1] = (b==w ? 1 : b==x ? 2 : b==y ? 3 : 4);
    res[2] = (c==w ? 1 : c==x ? 2 : c==y ? 3 : 4);
    res[3] = (d==w ? 1 : d==x ? 2 : d==y ? 3 : 4);
    return res;
}
 
ai4 solve1(int z, int p, int a, int b){
    // Solve for [0, +, ?, ?]
    ai4 res = ask(z, a, b, p);
    ai4 r = {0, +1, 0, 0};
    if (res[0] < res[1]){
        if (res[2] < res[3]){
            r[2] = (res[1] < res[3] ? -1 : 0);
            r[3] = (res[0] < res[2] ? -1 : +1);
        }
        if (res[3] < res[2]){
            r[2] = (res[1] < res[2] ? 0 : -1);
            r[3] = 0;
        }
    }
    if (res[1] < res[0]){
        if (res[2] < res[3]){
            r[2] = +1;
            r[3] = (res[1] < res[2] ? +1 : -1);
        }
        if (res[3] < res[2]){
            r[2] = +1;
            r[3] = 0;
        }
    }
    return r;
}
ai4 solve2(int z, int a, int b, int c){
    // Solve for [0, 0/-, 0/-, a+]
    ai4 res = ask(a, b, z, c);
    ai4 r = {0, 0, 0, 0};
    if (res[1] < res[0]){
        r[1] = -1; r[2] = 0; r[3] = 0;
    }
    if (res[0] < res[1]){
        if (res[2] < res[3]){
            r[1] = -1; r[3] = 0;
            r[2] = (res[1] < res[3] ? 0 : -1);
        }
        if (res[3] < res[2]){
            r[1] = 0; r[3] = +1;
            r[2] = (res[1] < res[2] ? 0 : -1);
        }
    }
    return r;
}
ai4 solve3(int z, int a, int b, int c){
    // Solve for [0, 0/-, 0/-, a0/a-]
    ai4 res = ask(c, a, b, z);
    ai4 r = {0, 0, 0, 0};
    if (res[0] < res[1]){
        if (res[2] < res[3]){
            r[2] = 0;
            r[1] = r[3] = (res[0] < res[2] ? 0 : -1);
        }
        if (res[3] < res[2]){
            r[2] = -1;
            r[1] = r[3] = (res[0] < res[3] ? 0 : -1);
        }
    }
    if (res[1] < res[0]){
        if (res[2] < res[3]){
            r[2] = 0;
            r[1] = (res[1] < res[2] ? 0 : -1);
            r[3] = (r[1] == -1 ? +1 : r[1]-1);
        }
        if (res[3] < res[2]){
            r[2] = -1;
            r[1] = (res[1] < res[3] ? 0 : -1);
            r[3] = (r[1] == -1 ? +1 : r[1]-1);
        }
    }
    return r;
}
ai4 solve(int z, int a, int b, int c){
    // Solve for [0, ?, ?, ?]
    ai4 res = ask(z, a, b, c);
    if (res[0] > 2){ ai4 r = solve1(z, a, b, c); return r; }
    if (res[0] > 1){
        if (res[2] == 1){ ai4 r = solve1(z, b, a, c); swap(r[1], r[2]); return r; }
        else{ ai4 r = solve1(z, c, b, a); swap(r[1], r[3]); return r; }
    }
    if (res[1] == 4){
        if (res[2] == 2){ ai4 r = solve2(z, a, b, c); return r; }
        if (res[3] == 2){ ai4 r = solve2(z, a, c, b); swap(r[2], r[3]); return r; }
    }
    if (res[1] == 3){
        if (res[2] == 2){ ai4 r = solve3(z, a, b, c); return r; }
        if (res[3] == 2){ ai4 r = solve3(z, a, c, b); swap(r[2], r[3]); return r; }
    }
}
 
vector<int> v;
 
void Main(){
    int m, k; cin >> m >> k; int n = 1<<m;
    for (int i = 1; i <= n; i++){
        if (i == k){ continue; }
        v.push_back(i);
    } int vl = v.size();
    int c0 = 0, c1 = 1, c2 = 0;
    for (int i = 0; i < vl; i+=3){
        int i1 = i, i2 = (i+1)%vl, i3 = (i+2)%vl;
        int a = v[i1], b = v[i2], c = v[i3];
        ai4 res = solve(k, a, b, c);
        if (i < vl){
            if (res[1] < 0){ c0 += 1; }
            if (res[1] == 0){ c1 += 1; }
            if (res[1] > 0){ c2 += 1; }
        }
        if (i+1 < vl){
            if (res[2] < 0){ c0 += 1; }
            if (res[2] == 0){ c1 += 1; }
            if (res[2] > 0){ c2 += 1; }
        }
        if (i+2 < vl){
            if (res[3] < 0){ c0 += 1; }
            if (res[3] == 0){ c1 += 1; }
            if (res[3] > 0){ c2 += 1; }
        }
    }
    while (1){
        if (m == 2){
            if (c2 >= 2){ cout << "! N" << endl << flush; return; }
            if (c2 > c0){ cout << "! N" << endl << flush; return; }
            cout << "! Y" << endl << flush; return;
        }
        if (c2 == 0){ cout << "! Y" << endl << flush; return; }
        if (c0 == 0){ cout << "! N" << endl << flush; return; }
        if (c2 < n/2){ cout << "! Y" << endl << flush; return; }
        c2 -= n/2-1; c0 -= 1; m -= 1; n /= 2;
    }
}