티스토리 뷰

문제: 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점 받고 다른 문제 푸는 것이 현명하겠다.

코드 보기(encoder.cpp)

코드 보기(decoder.cpp)

저작자 표시
신고

'IOI > IOI2011' 카테고리의 다른 글

[IOI2011 Day2] Parrots 문제 고찰 및 해법  (1) 2013.07.24
[IOI2011 Day2] Elephants 해법  (0) 2013.07.24
[IOI2011 Day2] Crocodile 해법  (0) 2013.07.24
[IOI2011 Day1] Race 해법  (4) 2013.07.23
[IOI2011 Day1] Garden 해법  (3) 2013.07.23
[IOI2011 Day1] Ricehub 해법  (0) 2013.07.23
댓글
  • 프로필사진 김민수 ㅋㅋ문제 정말 재밌네요. Task 4까지는 위치 5비트에 나머지 3비트의 가중치를 각각 1, 10, 100으로 두고 각각의 수를 변환하면 10*N안에서 좀더 직관적으로 해결이 가능했습니다 2015.06.30 15:46 신고
댓글쓰기 폼