BOJ 34111 Multi Communication (JOISC 2024-2025 Day 3 P3)

한동안 학교 일로 바빴는데, 앞으로 문제를 더 열심히 풀어야겠다고 생각했다. 원래는 문제 여러 개를 풀고 묶어서 글로 썼는데, 이제부터는 더 문제 수가 적은 글들도 올라갈 것 같다.

Subtask 1

$N = 4$이고 $L \le 2$턴 안에 해결해야 한다.

 

처음에 자신이 parent인지 아는 사람은 딱히 문제가 없다. 나머지 사람은 $3$명이 있는데, 이들은 자신을 제외한 두 명에게 parent인지 물어볼 수 있고, 둘 다 parent가 아니라고 하면 질문을 안 해본 한 사람을 고르면 된다.

 

void st1(){
    const int n = 4, L = 2;
    printf("2\n");
    for(int P=1; P<=n; P++){
        printf("%d\n", P);
        for(int C=1; C<=n; C++){
            vector<int> who (n+1); /// 0: 모름, 1: 맞음, -1: 아님
            if(P==C) who[C] = 1;
            else who[C] = -1;
            for(int R=1; R<=L; R++){
                printf("%c ", P==C ? 'T' : 'F');
                int x = 1;
                while(who[x]) x++;
                printf("%d ", x);
                if(P==x) who[x] = 1;
                else who[x] = -1;
            }
            puts("");
        }
    }
}

 

Subtask 2

$N = 32$이고 $L \le 8$턴 안에 해결해야 한다. 아무래도 $\log N$ 정도에 비례하는 풀이를 찾아야 할 것 같다. 그렇다면 $L$이 $\log N + 3$인지 $2 \log N - 2$인지 조금 생각해 볼 필요가 있는데, Subtask 1에서 $L = 2 \log N - 2$였으므로 이 시간 복잡도로 풀면 좋을 것 같다.

 

그렇다면 실질적으로 얻을 수 있는 정보가 어떤 게 있는지 생각해 보자. 일단 가장 먼저 떠오르는 건 첫 라운드를 어떻게 하는가이다. 아무래도 xor이 $1$인 것들끼리 묶어서 하면 좋을 것 같다. (인덱스가 대충 $[0, 31]$ 범위라고 생각할 때의 이야기이다.) 이렇게 하면 parent가 $p$일 때, $p$와 $p \oplus 1$이 메시지 T를 본 상태가 된다. 이걸 빠르게 전파시키려면 어떻게 할까? 다음 턴에는 xor이 $2$인 걸 보면 된다. 그럼 이제 $p, p \oplus 1, p \oplus 2, p \oplus 3$이 T를 본 상태가 된다. 이걸 $4$, $8$에 대해서도 해 보자. 이러면 노드들이 어떤 정보를 얻을 수 있을까?

 

parent가 $p$일 때, 어떤 노드 $c$에 대해 $p$와 $c$의 이진수를 비교하자. 이때 가장 높은 비트부터 봤을 때 처음으로 다른 비트가 $2^b$의 비트라고 하자. 이때 $c$는 $b+1$번 턴에 처음으로 메시지 T를 본 상태가 된다는 것을 알 수 있다. 만약 네 턴 동안 T를 못 받았다면, 애초에 $2^4$의 비트가 다르다는 것을 알 수 있다.

 

여기서부터는 어떻게 할까? $p$와 $c$에서 다른 가장 높은 비트가 $b(p, c)$번 비트라고 하자. 이때 $b(p, c) \le 3$인 것들은 $p$의 $2^3$의 비트가 무엇인지를 알 것이다. 한 번의 라운드를 써서 이것을 $b(p,c) = 4$인 것에게 전달한다. 그러면 $b(p, c) = 4$인 것들은 $c \oplus 2^4$번 노드를 들으면 저 값을 알 수 있다. 한 번의 라운드를 사용한 뒤, 이제 모든 노드가 $p$의 $2^4, 2^3$의 자리 비트가 뭔지 안다. 여기서 $2^2$의 자리 비트가 무엇인지 알려면 이 과정을 비트를 하나 내려서 반복하면 된다. $b(p, c) \le 2$인 것들은 $p$의 $2^2$의 자리 비트를 전달한다. $b(p, c) \ge 3$인 것들은 앞에서 $2^4$, $2^3$의 자리 비트를 알아냈으므로, $b(p, c) \le 2$인 $c$ 하나를 생성하는 것이 가능하다. (그냥 $2^4$, $2^3$의 자리 비트를 사용하고 뒤 세 자리는 $0$으로 두면 될 것이다.) 그럼 해당 플레이어에게 $p$의 $2^2$ 자리 비트가 무엇인지도 들을 수 있다. 이 과정을 비트를 내리며 두 번 더 반복하면, $4$번의 턴을 더 써서 모든 플레이어가 $p$를 알아낼 수 있다.

 

void st2(){
    const int n = 32, L = 8, B = 4;
    printf("%d\n", L);
    for(int P=0; P<n; P++){
        printf("%d\n", P+1);
        for(int C=0; C<n; C++){
            if(C == P){
                for(int i=0; i<B; i++) printf("T %d ", C+1);
                /// 뒤 log N-1 번 턴에는 parent도 규칙에 맞게 전송해야 함을 유의하자
                for(int i=B-1; i>=0; i--) printf("%c %d ", ((P >> i) & 1) ? 'T' : 'F', P + 1);
                puts("");
                continue;
            }
            int lb = B;
            while(((P>>lb)&1) == ((C>>lb)&1)) lb--;

            for(int i=0; i<B; i++){
                printf("%c %d ", i>lb ? 'T' : 'F', (C ^ (1<<i)) + 1);
            }
            for(int i=B-1; i>=0; i--){
                int v = (2<<i)-1;
                /// C가 p의 i번 비트를 알 조건은 lb <= i이다
                /// 아는 경우에는 그 비트를 전송하고, 모르면 0을 전송한다
                printf("%c %d ", ((lb > i ? 0 : ((P >> i) & 1)) ? 'T' : 'F'), ((P & ~v) + 1));
            }
            puts("");
        }
    }
}

 

Subtask 3

Subtask 2와 느낌은 비슷하나, 한 턴을 더 쓸 수 있고, 그 대가로 $N$이 $1.5$배 커졌다.

 

일단 $N$이 $2$의 완벽한 거듭제곱이 아닌 것부터 좀 불편하다. 그래도 $2^4 \times 3$이니까, Subtask 2의 전반부를 돌리는 데는 문제가 없다.

 

각 플레이어의 번호를 $5$비트로 보되, 첫 자리에 $0, 1, 2$가 들어갈 수 있다고 생각하자. Subtask 2의 전반부를 네 턴에 걸쳐 실행하면, $2^4$의 비트가 같은 수들은 정보를 조금 얻지만, $2^4$의 비트가 다른 것들은 그 다른 $2^4$의 비트에 대해 두 개의 후보가 생긴다. (즉, $p$의 $2^4$ 비트가 $0$이라 할 때, 네 턴이 지난 이후 $c$의 $2^4$ 비트가 $1$인 $c$들은 $p$의 $2^4$ 비트가 $0$인지 $2$인지 구분할 수 없다.)

 

한 턴을 더 써서 이 부분이 가능하게 할 것이다. 일단 $b(p, c) \le 3$인 것들은 모두 메시지를 받은 상태이다. 이제 마지막 한 턴은 cyclic하게 구성을 해서, $2^4$ 자리 비트가 $0$인 것들은 그 자리를 $1$로 바꾼 것들을 확인하고, $1$인 것들은 $2$로 바꾼 것들을 확인하고, $2$인 것들은 $0$으로 바꾼 것들을 확인한다. 이렇게 하면, $b(p, c) = 4$인 것들은 자신이 본 쪽이 T인지 F인지를 통해 $p$의 $2^4$ 비트를 알아낼 수 있다.

 

나머지 과정은 Subtask 2와 같다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void st1();
void st2();
void st3();

int main(){
    int n;
    cin>>n;
    if(n==4) st1();
    else if(n==32) st2();
    else st3();
}

void st1(){
    const int n = 4, L = 2;
    printf("2\n");
    for(int P=1; P<=n; P++){
        printf("%d\n", P);
        for(int C=1; C<=n; C++){
            vector<int> who (n+1); /// 0: 모름, 1: 맞음, -1: 아님
            if(P==C) who[C] = 1;
            else who[C] = -1;
            for(int R=1; R<=L; R++){
                printf("%c ", P==C ? 'T' : 'F');
                int x = 1;
                while(who[x]) x++;
                printf("%d ", x);
                if(P==x) who[x] = 1;
                else who[x] = -1;
            }
            puts("");
        }
    }
}

void st2(){
    const int n = 32, L = 8, B = 4;
    printf("%d\n", L);
    for(int P=0; P<n; P++){
        printf("%d\n", P+1);
        for(int C=0; C<n; C++){
            if(C == P){
                for(int i=0; i<B; i++) printf("T %d ", C+1);
                /// 뒤 log N-1 번 턴에는 parent도 규칙에 맞게 전송해야 함을 유의하자
                for(int i=B-1; i>=0; i--) printf("%c %d ", ((P >> i) & 1) ? 'T' : 'F', P + 1);
                puts("");
                continue;
            }
            int lb = B;
            while(((P>>lb)&1) == ((C>>lb)&1)) lb--;

            for(int i=0; i<B; i++){
                printf("%c %d ", i>lb ? 'T' : 'F', (C ^ (1<<i)) + 1);
            }
            for(int i=B-1; i>=0; i--){
                int v = (2<<i)-1;
                /// C가 p의 i번 비트를 알 조건은 lb <= i이다
                /// 아는 경우에는 그 비트를 전송하고, 모르면 0을 전송한다
                printf("%c %d ", ((lb > i ? 0 : ((P >> i) & 1)) ? 'T' : 'F'), ((P & ~v) + 1));
            }
            puts("");
        }
    }
}

void st3(){
    const int n = 48, L = 9, B = 4;
    printf("%d\n", L);
    for(int P=0; P<n; P++){
        printf("%d\n", P+1);
        for(int C=0; C<n; C++){
            if(C == P){
                for(int i=0; i<=B; i++) printf("T %d ", C+1);
                /// 뒤 log N-1 번 턴에는 parent도 규칙에 맞게 전송해야 함을 유의하자
                for(int i=B-1; i>=0; i--) printf("%c %d ", ((P >> i) & 1) ? 'T' : 'F', P + 1);
                puts("");
                continue;
            }
            int lb = B+1, S = C>>B, T = C&((1<<B)-1);
            while(((P>>lb)&1) == ((C>>lb)&1)) lb--;
            if(lb==B+1) lb = B;

            for(int i=0; i<B; i++){
                printf("%c %d ", i>lb ? 'T' : 'F', (C ^ (1<<i)) + 1);
            }
            printf("%c %d ", lb < B ? 'T' : 'F', (((S+1)%3)<<4 | T) + 1);

            for(int i=B-1; i>=0; i--){
                int v = (2<<i)-1;
                /// C가 p의 i번 비트를 알 조건은 lb <= i이다
                /// 아는 경우에는 그 비트를 전송하고, 모르면 0을 전송한다
                printf("%c %d ", ((lb > i ? 0 : ((P >> i) & 1)) ? 'T' : 'F'), ((P & ~v) + 1));
            }
            puts("");
        }
    }
}