[IOI2011 Day2] Parrots 문제 고찰 및 해법

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/parrots.pdf

• 서브태스크1 (17 점)
  
  배열에 저장되어 있는 변수가 0 또는 1이다. 따라서 값이 1인 것의 위치들을 넘겨주면 된다. 위치는 0부터 7 사이의 정수이므로 넘겨주는데 별다른 무리는 없다. 이 때 호출 회수는 최대 N이 된다.
  
  
• 서브태스크2 (17 점)
  
  이제, 배열에 저장되어 있는 변수는 0 이상 255 이하이고, N은 16이하다. 변환된 수는 0 이상 65536 이하이다. 변환된 수는 총 16비트를 가질 수 있다. 위치를 나타내는 4비트, 값을 나타내는 8비트, 총 12비트를 사용하여 각 위치에 어떤 값을 가지고 있는지 변환할 수 있다. 이 때 호출 회수는 N이 된다.
  
  
• 서브태스크3 (18 점)
  
  수의 비트 수는 8비트이다. 이를 2비트씩 4조각 낼 수 있다. 변환은 위치를 나타내는 4비트, 조각 번호를 나타내는 2비트, 조각의 값을 나타내는 2비트, 총 8비트의 수로 할 수 있다. 이 때 호출 회수는 4*N이 된다.
  
  
• 서브태스크4 (29 점)
  
  수의 비트 수는 8비트이다. 이를 1비트씩 8조각 낼 수 있다. 각 조각이 가질 수 있는 값은 0 또는 1이다. 우리는 조각의 값이 1일 때만 조각의 정보를 변환해서 보내면 된다. 위치를 나타내는 5비트, 조각 번호를 나타내는 3비트, 총 8비트의 수로 변환한다. 조각에 대한 정보가 변환되어 들어오면 조각의 값은 1이 되고, 변환되어 들어오지 않으면 조각의 값을 0으로 한다.

각 서브태스크에 대해 코딩 해줄 필요가 없다. 서브태스크4의 방법으로 서브태스크1,2,3,4 모두 해결할 수 있기 때문이다. 하지만 서브태스크 5는 따로 코딩을 해줘야한다. 사실 서브태스크4까지 해결하기는 쉽다. 서브태스크5를 어떤 아이디어로 해결하느냐가 점수를 정한다. 나는 대회 때 서브태스크4의 방법에 얽매이고, 간단한 아이디어를 생각하지 못해 89점을 받았다. (실제로 88점을 받을 해법이지만, 어째서인지 89점이다...)

1. P=12 방법 (총 88점)
   
   수의 비트 수는 8비트이다. 이를 2비트씩 4조각 낼 수 있다. 각 조각의 가질 수 있는 값은 0, 1, 2 그리고 3이다. 우리는 조각의 정보를 변환해서 넘겨주는데, 조각의 정보가 '몇 개' 변환되어 넘어 왔는지가 조각의 값을 결정한다. 하나도 넘어 오지 않으면 조각의 값은 0, 한 개가 넘어오면 값은 1, 2개면 값은 2, 3개면 값은 3. 이 때 P는 최악에 12가 된다.
   
   
2. P=6.25 방법 (총 98점)
   
   P=12의 방법과 거의 '동일'하다. 아주 간단하지만 생각이 잘 안날 수 있는 아이디어가 필요하다. 앞의 방법에서 조각의 값을 조각 정보의 개수로 전달했다. 이 때 변환된 수의 개수를 반으로 줄일 수 있다. 앞의 방법과 그를 뒤집어서 정보를 보낼 때 어느 쪽이 변한된 수의 개수가 적은지 판단을 하면 된다. 뒤집어서 정보를 보낸다는 것은, 조각의 정보가 하나도 넘어 오지 않으면 조각의 값을 3으로, 한 개가 넘어오면 값을 2, 2개면 값을 1, 3개면 값을 0으로 하는 방법이다. 그러면 두 방법 중 한 방법은 $6N$이하의 길이로 메시지를 변환한다. 하지만 우리는 두 방법 중 어떤 방법으로 변환하는지에 대한 정보가 필요하다. 이 두 방법 모두 변한된 수 하나가 3번 넘게 호출되지는 않는다. 이를 이용해 어떤 방법으로 변환했는지를 알려줄 수 있다. 만약 두 번째 변환 방법을 선택했다면 추가로 255를 4번 호출하는 방식으로 알려줄 수 있다. 이 때 $6N$ 이외에 4번의 추가 변환된 수가 필요하므로 $P=\frac{6N+4}{N}=6.25$ 이다.
   
   
3. 새로운 접근 (총 98점)
   
   중복 조합을 이용해 하나의 수를 7개의 변환된 수로 나타낼 수 있다. 0부터 3까지 4개의 수와 공백을 쓰는 중복 조합이 있다고 하자. 가능한 중복 조합의 개수는 ${{7+4}\choose{7}}=330$ 이다. 그리고 하나의 수는 0부터 255까지 256 경우가 있으므로, 수와 중복 조합의 한 경우와 매치하기기 충분하다. 즉, 256개의 수를 정의역, 330 가지 중복 조합을 치역으로 생각했을 때 단사 함수 $f$를 만들 수 있다. 처음 수가 64개까지 있을 수 있는데 이는 0부터 3을 첫번째 수가, 4부터 7을 두번째 수가 사용하도록 중복조합을 꾸리면 해결하능하다. 이 때 최대 비율 $P=7$이다.
   
   
4. 최적의 P (총 100점)
   
   3번 방법을 좀 더 최적화하면 만점을 받을 수 있다. 3번 방법에서는 하나의 수를 중복 조합으로 변환하는 단사 함수를 만들었는데, 이번엔 64개의 수를 모두 한꺼번에 중복 조합으로 변환하는 단사 함수를 만들면된다. 중복 조합이 가질 수 있는 값은 0부터 255까지 256개의 수와 공백이다. 따라서 크기가 261인 중복 조합이 있으면 이론상 64개의 수를 매치할 수 있다. ${{261+256}\choose{261}}={{517}\choose{261}}\approx1.47\times10^{154}$ 개의 중복 조합이 있고, $256^{64}\approx1.34\times10^{154}$ 이다. 따라서 이론적으로 단사함수 $f$를 만들 수 있고, 이 때 $P=\frac{261}{64}\simeq4.08$ 이다. 여기서 코딩의 편의를 위해 공백을 포함한 257개의 원소가 아닌 공백을 제외한 256개의 원소로 중복조합을 해도 100점을 받을 수 있다.
   
   

여지껏 여러 문제의 해법을 포스팅했지만, 가장 정성을 들여 작성한 글이다. 문제가 워낙 재미있고, 여러 사람에게 알려주고 싶어 들뜬 마음으로 글을 썼다. IOI 은메달리스트 중에도 이 문제를 100점 받은 사람들이 있어 신기하다. 사실 이 문제는 만점받기 힘든 문제지, 고득점하기는 쉬운 문제라 생각한다. 만점을 받는다고 해서 등수가 많이 오르는 것이 아니다. 98점 받기 쉬울 지 몰라도 100점 받기는 매우 어려운 문제라 대회라면 98점 받고 다른 문제 푸는 것이 현명하겠다.

#include "encoder.h" #include "encoderlib.h" struct BIGINT{ const static int maxlen = 99; int v[maxlen]; BIGINT(int n=0){ for (int i=0;i<maxlen;i++) v[i] = 0; int c = 0; for (;n;n>>=8) v[c++] = n&255; } bool operator < (const BIGINT &ot)const{ for (int i=maxlen;i--;) if (v[i] != ot.v[i]) return v[i] < ot.v[i]; return 0; } BIGINT operator + (const BIGINT &ot)const{ BIGINT a; for (int i=0;i<maxlen;i++) a.v[i] = v[i] + ot.v[i]; a.relax(); return a; } BIGINT operator - (const BIGINT &ot)const{ BIGINT a; for (int i=0;i<maxlen;i++) a.v[i] = v[i] - ot.v[i]; a.relax(); return a; } void relax(){ for (int i=0;i<maxlen-1;i++) while (v[i] < 0) v[i] += 256, v[i+1]--; for (int i=0;i<maxlen-1;i++){ v[i+1] += v[i]>>8; v[i] &= 255; } } }; static BIGINT D[264][256]; static bool init_sw; static void init() { if (init_sw) return; init_sw = 1; D[0][255] = BIGINT(1); for (int i=1;i<264;i++){ BIGINT sum; for (int j=256;j--;){ sum = sum+D[i-1][j]; D[i][j] = sum; } } } void encode(int N, int A[]) { init(); BIGINT mynum; for (int i=0;i<N;i++) mynum.v[i] = A[i]; int len = 0; for (int i=1;;i++) if (mynum < D[i+1][0]){ len = i; break; } int last = 0; for (int i=len;i>0;i--){ for (int j=last;j<256;j++){ if (!(mynum < D[i][j])) mynum = mynum - D[i][j]; else{ send(j); last = j; break; } } } }

#include "decoder.h" #include "decoderlib.h" #include <algorithm> using namespace std; struct BIGINT{ const static int maxlen = 99; int v[maxlen]; BIGINT(int n=0){ for (int i=0;i<maxlen;i++) v[i] = 0; int c = 0; for (;n;n>>=8) v[c++] = n&255; } bool operator < (const BIGINT &ot)const{ for (int i=maxlen;i--;) if (v[i] != ot.v[i]) return v[i] < ot.v[i]; return 0; } BIGINT operator + (const BIGINT &ot)const{ BIGINT a; for (int i=0;i<maxlen;i++) a.v[i] = v[i] + ot.v[i]; a.relax(); return a; } BIGINT operator - (const BIGINT &ot)const{ BIGINT a; for (int i=0;i<maxlen;i++) a.v[i] = v[i] - ot.v[i]; a.relax(); return a; } void relax(){ for (int i=0;i<maxlen-1;i++) while (v[i] < 0) v[i] += 256, v[i+1]--; for (int i=0;i<maxlen-1;i++){ v[i+1] += v[i]>>8; v[i] &= 255; } } }; static BIGINT D[264][256]; static bool init_sw; void init() { if (init_sw) return; init_sw = 1; D[0][255] = BIGINT(1); for (int i=1;i<264;i++){ BIGINT sum; for (int j=256;j--;){ sum = sum+D[i-1][j]; D[i][j] = sum; } } } void decode(int N, int L, int X[]) { init(); BIGINT mynum; sort(X, X+L); int last = 0; for (int i=0;i<L;i++){ for (int j=last;j<X[i];j++) mynum = mynum+D[L-i][j]; last = X[i]; } for (int i=0;i<N;i++) output(mynum.v[i]); }