IOI2020 Day2 mushrooms 풀이

문제 및 채점: oj.uz

 

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

 

10점 풀이

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

 

#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$번 하게 된다.

 

#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번이다.

 

#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번이다.

 

#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번이다.

 

#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를 구한 코드도 첨부한다.

 

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)

 

#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)); }