[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;
    }
}