IOI2020 Day2 mushrooms 풀이

문제 및 채점: oj.uz

 

번호가 0부터 $N-1$까지 매겨진 버섯 $N$ 개가 있다. 버섯은 두 종류로 구분할 수 있는데 눈으로 구분하기 힘들다. 기계를 사용하여 임의의 버섯들을 선택하여 순서를 정해 일렬로 기계에 넣을 수 있다. 기계에 넣으면 인접한 버섯 중에 종류가 다른 경우가 몇 개인지 확인하여 알려준다. 기계를 잘 사용하여 버섯 0과 같은 종류의 버섯 수가 몇 개인지 구하는 문제다.

 

10점 풀이

1 이상 $N-1$ 이하인 $i$에 대해 기계에 $[0, i]$ 순서로 버섯을 넣어 버섯 $i$가 버섯 0과 같은 종류인지 확인할 수 있다. 이때, 기계 사용을 최대 $19999$번 하게 된다.

 

?

1 2 3 4 5 6 7 8 9 10 11 12

#include <bits/stdc++.h> #include "mushrooms.h" using namespace std;   int count_mushrooms(int N) {     // Step 1: Check type of mushroom one by one     vector<int> arr[2] = {{0}, {}};     for (int i=1;i<N;i++)         arr[use_machine({0, i})].push_back(i);     return arr[0].size(); }

 

25점 풀이

10점 풀이에서 사용한 질문 형태로 최대 2번 안에 같은 종류를 가지는 버섯 쌍을 찾을 수 있다. 일반성을 잃지 않고 A 종류인 버섯 두 개를 찾았다고 하자. 기계에 $[A, x, A, y]$ 순서로 버섯을 넣고 결과값을 통해 $x$, $y$가 무슨 종류인지 알 수 있다. 만약 기계의 결과값이 0이라면 $x$, $y$는 모두 A 종류가 되고, 결과값이 1이라면 $x$는 A 종류, $y$는 B 종류가 된다. 결과값이 2라면 $x$는 B 종류, $y$는 A 종류가 되고, 결과값이 3이라면 $x$는 B 종류, $y$는 B 종류가 된다. 같은 종류를 가지는 버섯 쌍을 찾았을 때, 1번의 기계 사용으로 2개의 버섯의 종류를 알 수 있다. 이렇게 전체 버섯의 종류를 파악하면 기계 사용을 최대 $2+\lceil\frac{20000-3}{2}\rceil = 10001$번 하게 된다.

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

#include <bits/stdc++.h> #include "mushrooms.h" using namespace std;   int count_mushrooms(int N) {     vector<int> arr[2] = {{0}, {}};     int pt = 1;     // Step 1: Check type of mushroom one by one     while (pt < N){         arr[use_machine({0, pt})].push_back(pt);         pt++;         if (arr[0].size() >= 2 || arr[1].size() >= 2) break;     }     // Step 2: Check type of mushroom two by one     while (pt < N){         int t = arr[1].size() >= 2;         vector<int> test = {arr[t][0], pt, arr[t][1]};         if (pt+1 < N) test.push_back(pt+1);         int res = use_machine(test);         arr[res>>1&1^t].push_back(pt);         if (pt+1 < N) arr[res&1^t].push_back(pt+1);         pt += 2;     }     return arr[0].size(); }

 

80.43점 풀이

25점 풀이를 개선해보자. 각 버섯이 어떤 종류인지 구하는 것이 아니라, 버섯 0과 종류가 같은 버섯의 수를 구하는 문제다. 때문에 일정 수준까지 버섯의 종류를 파악하고 그 이후부터는 수만 세면 된다. 한 종류의 버섯을 $K$ 개 찾을 때까지 버섯의 종류 파악을 했다고 하자. $[A, a_1, A, a_2, A, a_3, \cdots, A, a_K]$ 순서로 기계를 사용하고 결과로 $r$ 값을 얻은 경우, $a_i$ 중에서 종류 B인 버섯의 수는 $\frac{r+1}{2}$이며, 반대로 종류 A인 버섯의 수는 $K-\frac{r+1}{2}$임을 알 수 있다. 이때, 최악의 경우 기계 사용 횟수를 제일 적게 할 수 있는 $K$ 값은 137이며, 그때 기계 사용 횟수는 최대 281번이다.

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

#include <bits/stdc++.h> #include "mushrooms.h" using namespace std;   int count_mushrooms(int N) {     int K = 137;     vector<int> arr[2] = {{0}, {}};     int pt = 1;     // Step 1: Check type of mushroom one by one     while (pt < N){         arr[use_machine({0, pt})].push_back(pt);         pt++;         if (arr[0].size() >= 2 || arr[1].size() >= 2) break;     }     // Step 2: Check type of mushroom two by one     while (pt < N){         int t = arr[1].size() >= 2;         vector<int> test = {arr[t][0], pt, arr[t][1]};         if (pt+1 < N) test.push_back(pt+1);         int res = use_machine(test);         arr[res>>1&1^t].push_back(pt);         if (pt+1 < N) arr[res&1^t].push_back(pt+1);         pt += 2;         if (arr[0].size() >= K || arr[1].size() >= K) break;     }     // Step 3: Count number of type 0 mushrooms K by one     int zero_count = arr[0].size();     while (pt < N){         int t = arr[1].size() >= K;         vector<int> test;         for (int i=0;pt+i<N&&i<K;i++){             test.push_back(arr[t][i]);             test.push_back(pt+i);         }         int res = use_machine(test);         int cnt = res+1>>1;         if (!t) cnt = test.size()/2-cnt;         zero_count += cnt;         pt += K;     }     return zero_count; }

 

92.62점 풀이

80.43점 풀이를 조금 개선해보자. $[A, a_1, A, a_2, A, a_3, \cdots, A, a_K]$ 순서로 기계를 사용하고 결과로 $r$ 값을 얻은 경우, 만약 $r$이 홀수라면 $a_K$는 B 종류이며, $r$이 짝수라면 $a_K$는 A 종류라는 것을 알 수 있다. 추가적으로 기계 사용 하나에 버섯 하나의 종류를 알 수 있다. 즉, 기계를 사용함에 따라 같은 종류인 버섯의 수가 점점 커지게 되기 때문에 뒤로 갈 수록 1번의 기계 사용으로 확인할 수 있는 버섯의 수가 늘어난다. 이때, 최악의 경우 기계 사용 횟수를 제일 적게 할 수 있는 $K$ 값은 81이며, 그때 기계 사용 횟수는 최대 244번이다.

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#include <bits/stdc++.h> #include "mushrooms.h" using namespace std;   int count_mushrooms(int N) {     int K = 81;     vector<int> arr[2] = {{0}, {}};     int pt = 1;     // Step 1: Check type of mushroom one by one     while (pt < N){         arr[use_machine({0, pt})].push_back(pt);         pt++;         if (arr[0].size() >= 2 || arr[1].size() >= 2) break;     }     // Step 2: Check type of mushroom two by one     while (pt < N){         int t = arr[1].size() >= 2;         vector<int> test = {arr[t][0], pt, arr[t][1]};         if (pt+1 < N) test.push_back(pt+1);         int res = use_machine(test);         arr[res>>1&1^t].push_back(pt);         if (pt+1 < N) arr[res&1^t].push_back(pt+1);         pt += 2;         if (arr[0].size() >= K || arr[1].size() >= K) break;     }     // Step 3: Count number of type 0 mushrooms many by one     int zero_count = arr[0].size();     while (pt < N){         int t = arr[1].size() > arr[0].size();         vector<int> test;         for (int i=0;pt+i<N&&i<arr[t].size();i++){             test.push_back(arr[t][i]);             test.push_back(pt+i);         }         int res = use_machine(test);         arr[res&1^t].push_back(test.back());         int cnt = res+1>>1;         if (!t) cnt = test.size()/2-cnt;         zero_count += cnt;         pt += test.size()/2;     }     return zero_count; }

 

100점 풀이

92.62점 풀이를 개선해보자. 그 풀이에서 한 종류의 버섯의 $K$ 개 찾는 과정 중 질문 1번의 기계 사용으로 버섯 2개의 종류를 판별할 수 있었다. 이는 2의 효율을 갖는다고 볼 수 있는데, 이 효율을 늘릴 수는 없을까?

 

Brute Force로 Decision Tree를 잘 만들어보니, 한 종류의 버섯이 3개 이상, 다른 종류의 버섯이 1개 이상인 경우, 2번의 기계 사용으로 버섯 5개의 종류를 판별하는 방법이 있다. 이는 2.5의 효율을 갖으며, 이전 방법보다 더 효율이 좋고, 전체적인 기계 사용 횟수를 감소시킬 수 있다.

 

그러면 한 종류의 버섯이 3개 이상, 다른 종류의 버섯이 1개 이상이 되기까지 어떤 식으로 기계를 사용할까? 이 또한 마찬가지로 Brute Force로 Decision Tree를 잘 만들어보니, 한 번의 기계 사용으로 5개의 버섯이 같은 종류인지 확인하고 그중 하나라도 다른 종류가 있으면 기계 사용을 2번 더 하여 버섯 5개의 종류를 판별하는 방법이 있다.

 

만약 처음 검사하는 5개 중 다른 종류가 하나라도 있으면 그 즉시 한 종류의 버섯이 3개 이상, 다른 종류의 버섯이 1개 이상이 되며, 만약 모두 같은 종류라면 한 번의 기계 사용으로 버섯 5개의 종류를 알 수 있으니 오히려 더 좋은 상황이다.

 

이 방법에서 최악의 경우 기계 사용 횟수를 제일 적게 할 수 있는 $K$ 값은 97이며, 그때 기계 사용 횟수는 최대 226번이다.

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

#include <bits/stdc++.h> #include "mushrooms.h" using namespace std;   // Rules generated by using brute force map <vector<int>, string> rule3_1_2 = {     {{}, "A0B0C0D1E"},     {{1}, "0D"},     {{2}, "0A0D0E"},     {{3}, "0A1BC0E0D"},     {{4}, "0A0E0BC1D"},     {{5}, "0A0BC1E0D"},     {{6}, "0A0D0E"},     {{7}, "0D"} }; map <vector<int>, string> rule1_0_3 = {     {{}, "0ABCDE"},     {{1}, "0ABCD"},     {{1, 1}, "AB0C"},     {{2}, "A0BCD"},     {{2, 1}, "AB0CE"},     {{2, 2}, "ABDC"},     {{2, 3}, "0C"},     {{3}, "A0BCE"},     {{3, 1}, "0B"},     {{3, 2}, "0BDC"},     {{3, 3}, "0D"},     {{3, 4}, "0D"},     {{4}, "A0BCD"},     {{4, 2}, "0C"},     {{4, 3}, "0ABCD"} };   int eval(const string &choice, int msk, bool base) {     int n = choice.length();     vector <bool> arr(n);     for (int i=0;i<n;i++){         if (choice[i] == '0') arr[i] = base;         else if (choice[i] == '1') arr[i] = base^1;         else arr[i] = msk>>(choice[i]-'A')&1;     }     int ret = 0;     for (int i=1;i<n;i++) if (arr[i-1] != arr[i]) ret++;     return ret; }   int count_mushrooms(int N) {     int K = 97;     vector<int> arr[2] = {{0}, {}};     int pt = 1;     // Step 1: Check type of mushroom based on rule     while (N-pt >= 5 && max(arr[0].size(), arr[1].size()) < K){         int t = arr[1].size() > arr[0].size();         auto &rule = (             arr[t].size() >= 3 && arr[t^1].size() >= 1 ?                 rule3_1_2 :                 rule1_0_3         );         vector<int> path;         vector<bool> valid(32, 1);         while (rule.count(path)){             string command = rule[path];             vector<int> test, p(2);             for (char c: command){                 if (c == '0' || c == '1') test.push_back(arr[(c-'0')^t][p[(c-'0')^t]++]);                 else test.push_back(pt+(c-'A'));             }             int res = use_machine(test);             for (int i=0;i<32;i++) if (valid[i]){                 if (eval(command, i, t) != res) valid[i] = 0;             }             path.push_back(res);         }         int cnt = 0, msk;         for (int i=0;i<32;i++) if (valid[i])             cnt++, msk = i;         assert(cnt == 1);         for (int i=0;i<5;i++)             arr[msk>>i&1].push_back(pt+i);         pt += 5;     }     // Step 2: Count number of type 0 mushrooms many by one     int zero_count = arr[0].size();     while (pt < N){         int t = arr[1].size() > arr[0].size();         vector<int> test;         for (int i=0;pt+i<N&&i<arr[t].size();i++){             test.push_back(arr[t][i]);             test.push_back(pt+i);         }         int res = use_machine(test);         arr[res&1^t].push_back(test.back());         int cnt = res+1>>1;         if (!t) cnt = test.size()/2-cnt;         zero_count += cnt;         pt += test.size()/2;     }     return zero_count; }

 

참고

각 풀이에서 최악의 경우 기계 사용 횟수를 최소화 해주는 $K$ 값은 python으로 프로그래밍하여 구했다. 100점 풀이에서 가장 좋은 $K$를 구하는 python 코드를 첨부하며, 100점 풀이에서 Brute Force로 Decision Tree를 구한 코드도 첨부한다.

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

import math   def get(N, K, p, q):     cover = p+q     ret = 0     while cover < N:         cover += max(p, q)         ret += 1         if p < q:             p += 1         else:             q += 1     return ret   def calc(N, K):     ret = 0     _p = 1     _base = 0     while True:         if _p >= K:             ret = max(ret, _base+get(N, K, _p, 0))             break         for i in range(1, 6):             p = _p+5-i             q = i             val = _base + 3             while True:                 if max(p, q) >= K:                     break                 val += 2                 for _ in range(5):                     if p > q:                         q += 1                     else:                         p += 1             ret = max(ret, val+get(N, K, p, q))         _p += 5         _base += 1     return ret   N = 20000 mn = 10**9 for K in range(10, 300):     v = calc(N, K)     # print(K, v)     if mn > v:         mn = v         optK = K print(optK, mn)

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128

#include <bits/stdc++.h> using namespace std;   #define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)   const int X = 5; // 미지수 개수   map<int, vector<string>> get_choices(int x, int y) {     // X개가 한번 씩 등장하고 각 미지수 사이는 비어있거나 0, 1 한 개만 있을 수 있다     map <int, vector<string>> choices;     vector<char> arr;     for (int i=0;i<X;i++) arr.push_back(i+'A');     function<void(int, int, int, string, int)> dfs;     dfs = [&](int n, int x, int y, string cur, int msk){         if (n == X){             choices[msk].push_back(cur);             if (x > 0) choices[msk].push_back(cur+'0');             if (y > 0) choices[msk].push_back(cur+'1');             return;         }         if (msk>>n&1^1){             dfs(n+1, x, y, cur, msk);             return;         }         if (x > 0) dfs(n+1, x-1, y, cur+'0'+arr[n], msk);         if (y > 0) dfs(n+1, x, y-1, cur+'1'+arr[n], msk);         dfs(n+1, x, y, cur+arr[n], msk);     };     for (int msk=1;msk<(1<<X);msk++){         do{             dfs(0, x, y, "", msk);         }while(next_permutation(arr.begin(), arr.end()));     }     return choices; }   int eval(const string &choice, int msk) {     int n = choice.length();     vector <bool> arr(n);     for (int i=0;i<n;i++){         if (choice[i] == '0') arr[i] = 0;         else if (choice[i] == '1') arr[i] = 1;         else arr[i] = msk>>(choice[i]-'A')&1;     }     int ret = 0;     for (int i=1;i<n;i++) if (arr[i-1] != arr[i]) ret++;     return ret; }   bool get_decision_tree(int x, int y, int max_depth, bool just_check=0) {     auto choices = get_choices(x, y);       map <pair<int, uint64_t>, bool> cache;     function <bool(int, uint64_t)> dfs;     vector <pair<vector<int>, string>> should_do;     vector <int> path;     dfs = [&](int dep, uint64_t cur) -> bool{         if (cache.count({dep, cur})){             bool &ret = cache[{dep, cur}];             if (just_check) return ret;             if (!ret) return 0;         }         bool &ret = cache[{dep, cur}];           // 남은 경우의 수가 1개면 끝         if ((cur&(-cur)) == cur) return ret = 1;           // 정해둔 제한보다 깊게 들어가지 않는다         if (dep >= max_depth) return ret = 0;           int msk = 0;         for (int i=0;i<X;i++){             // 현재 상태에서 아직 i가 결정되지 않았는지 확인             int t = 0;             for (int j=0;j<(1<<X);j++) if (cur>>j&1){                 t |= 1<<(j>>i&1);             }             if (t == 3) msk ^= 1<<i;         }           // 결정 되지 않은 애들은 모두 질문에 등장하도록 커팅         for (const auto &c: choices[msk]){             map <int, uint64_t> res;             for (int i=0;i<(1<<X);i++) if (cur>>i&1){                 int v = eval(c, i);                 res[v] ^= (uint64_t)1<<i;             }             if (res.size() == 1) continue;             bool imp = 0;             int org_size = should_do.size();             if (!just_check) should_do.push_back({path, c});             for (auto &it: res){                 if (!just_check) path.push_back(it.first);                 if (!dfs(dep+1, it.second)) imp = 1;                 if (!just_check) path.pop_back();                 if (imp) break;             }             if (!imp){ return ret = 1; }             if (!just_check){                 while (should_do.size() > org_size) should_do.pop_back();             }         }         return ret = 0;     };     if (!dfs(0, ((uint64_t)1<<(1<<X))-1)) return 0;     for (auto &it: should_do){         printf("{{");         for (int i=0;i<it.first.size();i++){             printf("%d%s", it.first[i], i+1<it.first.size() ? ", " : "");         }         printf("}, ");         printf("\"%s\"},\n", it.second.c_str());     }     return 1; }   int main() {     // 1 0 3 ok     // 3 1 2 ok     // 3 0 2 fail     // 2 1 2 fail     // 2 2 2 ok (but better to use 3 1 2)     printf("%d\n", get_decision_tree(3, 1, 2)); }