Problem Solving Diary #24

인터랙티브 문제와 투스텝 문제 몇 개를 풀어보았다.

BOJ 31975. Staring Contest

만점을 받기 위해서는 $q \le n + 25$회 이내에 문제를 해결해야 한다. 데이터가 사전에 결정되어 있고 제한이 애매하므로 무작위화 알고리즘을 고려해볼 수 있다.

 

어떤 사람 $s$를 정하고, 이 사람과 다른 사람들에 대한 쿼리를 계속 날린다. 날리다가 이미 들어온 값 $v$가 또 들어오는 시점이 있을 것이다. 두 사람의 실력이 다르므로 이 값은 사람 $s$의 실력이라고 생각할 수 있을 것이다. 즉, 사람 $s$의 실력을 $v$로 고정할 수 있다. 또한 앞에서 쿼리를 날렸을 때 $v$보다 작은 값이 들어온 경우 그 값들을 해당 사람들의 실력으로 확정할 수 있을 것이다. 이제 $v$라는 결과가 나온 두 사람 중 하나를 $s$로 두고, 아직 답을 모르는 사람들에 대해 이 과정을 계속 반복하면 된다.

 

사람의 순서를 랜덤으로 섞어 무작위화 알고리즘을 적용한다. 실제로 쿼리 수를 추정하려면 다음 문제에 대한 해답을 구하면 된다.

• 길이 $n$의 순열 $A$를 무작위로 섞고, prefix max 배열 $P$를 만들었을 때, $P$에 있는 서로 다른 원소 개수의 기댓값이 얼마인가?

위 문제에 대한 답은 대략적으로 $O(\log n)$ 근처라고 추정할 수 있다. 어떤 배열의 최댓값의 위치는, 그 배열의 길이가 $l$이라고 할 때 평균적으로 $\frac{l}{2}$ 정도에 위치한다. 이 최댓값 뒤에 있는 수들은 답에 영향을 주지 않으므로, 최댓값 앞의 수만 본 뒤 같은 작업을 반복한다. 한 번 작업을 할 때마다 배열의 절반 정도가 줄어듬을 알 수 있으므로, 실제로 최댓값이 갱신되는 일은 평균적으로 $O(\log n)$번 정도일 것이라고 생각할 수 있다. 따라서 쿼리 횟수가 $n + \log n$ 정도라고 근사할 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
vector<int> indices;
int ans[1502];

int main(){
    scanf("%d", &n);

    int s = 1;
    vector<int> vec;
    for(int i=2; i<=n; i++) vec.push_back(i);
    random_shuffle(vec.begin(), vec.end());

    while(true){
        map<int, int> mp;
        bool duplicate = 0;
        while(!vec.empty()){
            int x = vec.back(); vec.pop_back();
            printf("? %d %d\n", s, x);
            fflush(stdout);
            int v;
            scanf("%d", &v);

            if(!mp.count(v)){
                mp[v] = x;
                continue;
            }
            duplicate = 1;
            for(auto [y, z]: mp) ans[z] = y;
            ans[s] = v;
            s = mp[v];
            vec.push_back(x);
            break;
        }
        if(duplicate) continue;
        for(auto [y, z]: mp){
            ans[z] = y;
        }
        ans[s] = mp.rbegin()->first;
        break;
    }
    printf("! ");
    for(int i=1; i<=n; i++) printf("%d ", ans[i]);
}

BOJ 10117. Question

문제

A에게는 $N \le 920$인 두 양의 정수 $x$와 $y$가 주어진다. A는 B에게 양의 정수 $h$를 보낼 수 있다.

 

B는 양의 정수 $h$와 정수 $q$를 받는다. $q$는 $q=x$ 또는 $q=y$인데, $h$를 보고 어느 쪽에 해당하는지 맞혀야 한다.

 

보내는 $h$의 범위를 최소화해 목표를 달성해 보자.

풀이

먼저 $h=20$인 경우의 풀이를 보자. $x$와 $y$는 서로 다르기 때문에, 이진수로 나타냈을 때 서로 다른 비트가 존재한다. 그 비트는 $2^0$부터 $2^9$까지의 비트 중 하나일 것이므로, 10가지 중 하나이다.

 

정수 $h$를 통해 해당 비트가 몇 번째 비트인지, 그리고 $x$에서 그 비트의 값이 무엇인지를 인코딩해 보낼 수 있다. 이때 $h$의 최댓값은 $10 \times 2 = 20$이 된다.

 

여기서 $h$의 최댓값을 $12$까지 끌어올리려면 다른 방법이 필요하다. ${}_{12} C_6=924$인 점을 이용해 보자. 길이가 $12$이고 $0$과 $1$이 각각 $6$개씩 있는 모든 문자열을 만들고, 그 중 사전순으로 $x$번째인 것과 $y$번째인 것을 보자. 이때 $x$번째 문자열에서는 $0$이지만 $y$번째 문자열에서는 $1$인 것이 반드시 존재한다. 그 위치를 $h$로 보낼 것이다. B는 받은 수 $q$의 $h$번째 자리를 보고, 그 자리가 $0$이면 yes, $1$이면 no를 출력하면 된다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

string s[924];
void init(){
    string A = "(((((())))))";
    int cnt = 0;
    do {
        s[cnt++] = A;
    } while(next_permutation(A.begin(), A.end()));
}

int m, n, t;
int x, y;

int main(){
    init();
    scanf("%d %d %d", &m, &n, &t);
    if(m==1){
        while(t--){
            int x, y;
            scanf("%d %d", &x, &y);
            int h = 0;
            while(s[x][h] == ')' || s[y][h] == '(') h++;
            printf("%d\n", h+1);
        }
    }
    else{
        while(t--){
            int q, h;
            scanf("%d %d", &q, &h);
            printf("%s\n", s[q][h-1] == '(' ? "yes" : "no");
        }
    }
}

BOJ 10232. Saveit

문제

• 정점이 $N$개인 그래프가 있다. 모든 간선은 양방향이며 가중치가 $1$이다.
• 앞 $H$개의 정점으로부터 다른 모든 정점까지의 최단거리를 모두 구할 수 있도록 짧은 길이의 비트스트링을 전달해야 한다.
• $N \le 1000$, $H \le 36$

풀이

Subtask 2까지는 모든 최단거리를 구해 전달해도 된다. 최단거리는 $1000$ 이하이므로 $10$비트로 전달할 수 있고, $10NH \le 360 , 000$ 비트 안으로 전달할 수 있다.

 

Subtask 3부터는 효율적인 방법이 필요하다. 다음 사실을 알 수 있다.

• 어떤 두 정점 $x$와 $y$가 인접하다면, 허브 $h$에서 $x$까지의 최단거리 $dist(h, x)$와 $y$까지의 최단거리 $dist(h, y)$는 최대 1 차이난다.

따라서, 다음과 같은 방법을 생각해볼 수 있다: 임의의 스패닝 트리 $T$를 잡고, $T$에서 각 정점들의 부모 노드를 인코딩한다. 여기에 $1000 \times 10$ 개의 비트가 필요하다. 이후 각 허브에 대해 다음을 인코딩한다.

• $T$의 루트 노드까지의 거리 ($10$ 비트)
• $T$의 루트 노드가 아닌 각 노드에 대해, 부모 노드의 최단거리와 자기 노드의 최단거리의 차이 ($-1$, $0$, $1$ 중 하나) ($999 \times 2$ 비트)

위와 같이 하면 허브 하나당 대략 $2000$ 비트를 이용해 인코딩할 수 있다. 이렇게 하면 약 $82000$ 비트가 필요하다. 스패닝 트리 $T$를 정점 $0$에서 시작하는 BFS 트리로 잡으면 $2000$ 비트를 아낄 수 있으므로 약 $80000$ 비트 정도가 필요할 것이다. 이걸로 Subtask 3을 맞을 수 있는지는 잘 모르겠다. 아마 몇 비트를 더 아껴야 될 수도 있다. 이 부분이 그렇게 어려워 보이진 않는다.

 

여기서 가장 쉽게 줄일 수 있는 부분은 저 $999 \times 2$ 비트를 줄이는 것이다. 이론적으로는 $\log_2 {3^{999}}$ 비트가 필요하고, 이것은 약 $1583.4 $ 정도이므로 노드당 $1584$ 비트 정도면 충분하다. 이 정도면 문제를 풀기에는 충분하지만, 큰 수를 구현해야 하므로 그다지 실용성이 있어 보이진 않는다. 가장 그럴듯한 방법은 $3^i \sim 2^j$인 $(i, j)$ 쌍을 찾아 수 $i$개의 정보를 $j$비트에 담는 것이다. 예를 들어, $3^5$는 $2^8$보다 약간 작으므로 5개의 정보를 8비트에 담을 수 있을 것이다. 이렇게 하면 각 허브당 $1000 \div 5 \times 8 = 1600$ 비트가 필요하고, 이 정도로도 만점을 받기에 충분하다.

#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>

using namespace std;

namespace {
    int n, h, m;
    vector<int> link[1002];
    int par[1002];
    bool visited[1002];
    int dist[50][1002];
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
    n = nv, h = nh, m = ne;
    for(int i=0; i<m; i++){
        link[v1[i]].push_back(v2[i]);
        link[v2[i]].push_back(v1[i]);
    }

    /// BFS 트리를 인코딩
    queue<int> que;
    que.push(0), visited[0] = 1;
    while(!que.empty()){
        int x = que.front(); que.pop();
        for(int y: link[x]){
            if(visited[y]) continue;
            visited[y] = 1, par[y] = x;
            que.push(y);
        }
    }
    for(int i=1; i<n; i++) for(int j=0; j<10; j++) encode_bit((par[i]>>j)&1);

    /// 거리 차이를 인코딩
    for(int s=0; s<h; s++){
        fill(visited, visited+n+1, 0);
        que.push(s), visited[s] = 1, dist[s][s] = 0;
        while(!que.empty()){
            int x = que.front(); que.pop();
            for(int y: link[x]){
                if(visited[y]) continue;
                visited[y] = 1, dist[s][y] = dist[s][x] + 1;
                que.push(y);
            }
        }
        /// dist[s][0] 인코딩
        for(int i=0; i<10; i++) encode_bit((dist[s][0]>>i)&1);
        /// 나머지 거리 인코딩
        vector<int> vec;
        for(int i=1; i<n; i++){
            int v = dist[s][i] - dist[s][par[i]] + 1;
            vec.push_back(v);
            if((int)vec.size() == 5){
                int val = vec[0] + vec[1]*3 + vec[2]*9 + vec[3]*27 + vec[4]*81;
                for(int d=0; d<8; d++) encode_bit((val>>d)&1);
                vec.clear();
            }
        }
        if(!vec.empty()){
            vec.resize(5);
            int val = vec[0] + vec[1]*3 + vec[2]*9 + vec[3]*27 + vec[4]*81;
            for(int d=0; d<8; d++) encode_bit((val>>d)&1);
            vec.clear();
        }
    }
}

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>

using namespace std;

namespace {
    int n, h;
    vector<int> link[1002];
    int par[1002];
    int offset[50][1002];
    int dist[50][1002];

    void dfs(int x){
        for(int y: link[x]){
            for(int s=0; s<h; s++) dist[s][y] = dist[s][x] + offset[s][y];
            dfs(y);
        }
    }
}

void decode(int nv, int nh){
    n = nv, h = nh;
    for(int i=1; i<n; i++){
        int v = 0;
        for(int d=0; d<10; d++) v += decode_bit() << d;
        par[i] = v;
        link[v].push_back(i);
    }
    for(int s=0; s<h; s++){
        for(int d=0; d<10; d++) dist[s][0] += decode_bit() << d;
        for(int l=1; l<n; l+=5){
            int v = 0;
            for(int d=0; d<8; d++) v += decode_bit() << d;
            for(int x=l; x<l+5 && x<n; x++){
                offset[s][x] = v % 3 - 1;
                v /= 3;
            }
        }
    }
    dfs(0);
    for(int s=0; s<h; s++){
        for(int i=0; i<n; i++){
            hops(s, i, dist[s][i]);
        }
    }
}

BOJ 23407. Board Trick

notorious coincidence를 예전에 본 적이 있고, 그 뒤로 유튜브에서도 본 적 있던 문제로 기억한다.

 

편의상 모든 칸의 인덱스를 $0$부터 $63$으로 두자. 수가 $1$인 부분의 인덱스를 모두 XOR 했을 때 $v$가 되도록 하면 된다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

string s;
int t, n;
int board[64];

int main(){
    cin >> s;
    if(s == "Mia"){
        scanf("%d", &t);
        while(t--){
            int v = 0;
            for(int i=0; i<64; i++){
                scanf("%d", &board[i]);
                if(board[i]) v ^= i;
            }
            scanf("%d", &n); n--;
            board[n^v] ^= 1;
            for(int i=0; i<64; i++){
                printf("%d%c", board[i], i%8==7 ? '\n' : ' ');
            }
            puts("---");
        }
    }
    else{
        scanf("%d", &t);
        while(t--){
            int v = 0;
            for(int i=0; i<64; i++){
                scanf("%d", &board[i]);
                if(board[i]) v ^= i;
            }
            printf("%d\n", v+1);
            cin >> s;
        }
    }
}