IOI 2018 4번) Mechanical Doll

https://www.acmicpc.net/problem/20064

20064번: Mechanical Doll

<Step 1> Switch의 성질 관찰

 

Switch는 다시 초기 상태로 돌아와야 하기 때문에, 공이 짝수 번 들어와야 합니다.

Switch에 공이 2a번 들어왔다면, X로 a번, Y로 a번 공이 나갑니다.

 

<Step 2> Switch를 이용한 작은 기계 만들어보기

 

문제를 풀기 위해 큰 기계를 만들어보기 전에, 공이 들어왔을 때 순서대로 1, 2, .., n번 trigger로 이동하는 기계를 만들어봅시다.

 

n = 2일 때 : 

n = 3일 때 :

N = 3일 때 -1번 Switch에 들어오는 공의 개수에 주목해봅시다. 3개의 공이 들어오고 -2번 Switch에서 1개가 돌려보내져서 총 4개의 공이 들어옵니다.

 

-2번, -3번 Switch는 각각 2개의 공이 들어오고, 각 방향으로 1개의 공을 내보냅니다.

 

<Step 3> Switch를 이용한 큰 기계 설계하기

 

공이 i번째로 들어올 때, A[i-1]번으로 가게 하는 기계를 설계해봅시다. 기계에 공이 N번 들어올 때 원하는 위치로 보내줘야 합니다.

 

N이 2의 거듭제곱일 때는 자명합니다. 공이 들어오는 순서대로 1, 2, 3, ... 단계 Switch라고 할 때, 1단계 Switch의 출구를 모두 2단계 Switch, 2단계 Switch의 출구를 모두 3단계 Switch로 정하는 걸 반복해주면 됩니다.

 

N이 2의 거듭제곱이 아닐 때는 어떻게 할까요? 1단계 Switch에 들어오는 공을 억지로 2의 거듭제곱으로 만들어야 합니다. 2, 3, ... 단계 Switch에는 1단계 Switch의 1/2, 1/4, ....만큼의 공이 들어오는데, 그럼 적절하게 역으로 1단계 Switch로 보내주면 됩니다. 비트마스킹을 이용해 N을 이진수로 표현하고, 보내줘야 할 Switch를 적절히 선택하면 최대 N + log N개의 Switch로 기계를 설계할 수 있습니다.

 

<Step 4> 기계 Simulate해보기

 

기계를 완성한다고 해도, 기계에 들어온 공이 어느 곳으로 나갈지 구하기 쉽지 않습니다. 그래서, 그냥 직접 공을 굴려봅니다. 들어가는 순서대로 A[0], A[1], ...로 나가는 출구를 배정해주면 됩니다.

 

<소스 코드>

#include "doll.h"
#include <queue>
#include <stdio.h>

int x[400002], y[400002];

void change(int M, std::vector<int> &C, std::vector<int> &X, std::vector<int> &Y, std::vector<int> A){
    std::queue<int> q;
    A.push_back(0);
    int L = (int)A.size();

//trigger에 공이 들어가면, 모두 -1번 Switch로 보낸다.
    for(int i=0;i<=M;i++) C[i] = -1;

    for(int i=0;i<=400000;i++){
        x[i] = 1;
        y[i] = 1;
    }

    int h = 0;
    while((1<<h) < L) h++;
    L = (1<<h) - L;

    q.push(1);

    int cnt = 1;

//기계를 설계한다.
    for(int i=h-1;i>=0;i--){
        std::queue<int> temp;
        int now = q.front(); q.pop();
        if(i == 0 && (1&L)){
            x[now] = -1;
        }
        if(i == 0) break;

        if((1<<i) & L){
            x[now] = -1;
            ++cnt; y[now] = -cnt; temp.push(cnt);
        }
        else{
            ++cnt; x[now] = -cnt; temp.push(cnt);
            ++cnt; y[now] = -cnt; temp.push(cnt);
        }
        while(!q.empty()){
            int now = q.front(); q.pop();
            ++cnt; x[now] = -cnt; temp.push(cnt);
            ++cnt; y[now] = -cnt; temp.push(cnt);
        }
        while(!temp.empty()){
            int now = temp.front(); temp.pop();
            q.push(now);
        }
    }

    std::vector<bool> visited(cnt);
    X.resize(cnt); Y.resize(cnt);

    for(int i=0;i<cnt;i++){
        X[i] = x[i+1];
        Y[i] = y[i+1];
    }

//설계한 기계에 공을 흘려보낸다.
    for(int i=0;i<(1<<h) - L;i++){
        int curr = -1;
        for(;;){
            if(!visited[-curr-1]){
                visited[-curr-1] = true;
                if(x[-curr] == 1) { X[-curr-1] = A[i]; break; }
                else curr = x[-curr];
            }
            else{
                visited[-curr-1] = false;
                if(y[-curr] == 1) { Y[-curr-1] = A[i]; break; }
                else curr = y[-curr];
            }
        }
    }
}

void create_circuit(int M, std::vector<int> A) {
    std::vector<int> C(M + 1);
    std::vector<int> X, Y;
    change(M, C, X, Y, A);
    answer(C, X, Y);
}