<div id="readability-page-1" class="page"><div>문제 및 채점: <a href="https://oj.uz/problem/view/IOI20_mushrooms" target="_blank" rel="noopener">oj.uz</a>

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

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



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



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



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



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



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



</div></div>

PS 이야기

문제 및 채점: 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));
}

IOI2020 Day2 mushrooms 풀이

댓글