문제 셋 : 2011 IOI day2
oj.uz - 문제
로그인 회원가입
oj.uz
5시간 동안 풀어서 Crocodile 100점, Elephants 26점, Parrots 98점을 받았습니다.
Crocodile
이 문제를 푸는 가장 핵심적인 접근은 바로 탈출방에서부터 거꾸로 각 방의 최소 탈출시간을 하나씩 확정해 나가는 방식입니다. 탈출시간을 결정하는 요소는 현재의 위치밖에 없으므로 다익스트라와 같은 방식으로 탈출시간이 0인 탈출방으로부터 연결된 방으로 한칸씩 확장해나가는 방식이 유효합니다. 이때 중요한 점은 악어가 간선을 막을 수 있으므로 방의 탈출시간이 확정될 때는 연결된 탈출경로중 길이가 두 번째로 짧은 경로를 선택해야 한다는 것입니다. 이걸 N^2으로 그대로 짜면 89점을 받을 수 있고, 여기에 우선순위 큐등을 이용하여 O(N lg N)으로 줄이면 100점을 받을 수 있습니다.
Elephants
우선 코끼리들의 배열이 주어지면 여기서 최소 사진기의 수를 찾아내는 것은 앞쪽부터 그리디하게 찾아주면 O(N)에 쉽게 가능합니다. 이를 이용해서 업데이트마다 O(N)으로 코끼리들을 관리해주면 O(NQ)의 시간복잡도로 문제를 해결할 수 있고 총 26점을 받을 수 있습니다. 시간을 줄이기 위해서는 업데이트를 빠르게 해줄 수 있어야 하는데 이 경우 보통 세그먼트 트리등을 생각해 볼 수 있습니다. 하지만 이 문제에서는 코끼리들의 순서가 계속해서 바뀌는데다가 앞쪽의 한 코끼리가 변하면 뒤쪽의 다른 코끼리들에 대해서도 모두 변하므로 적용이 쉽지 않아 보입니다. 하지만 여기서 9초라는 널널한 시간제한에서 O(sqrt(N))의 가능성을 생각해 볼 수 있습니다. 코끼리들을 sqrt(N)개 정도의 버킷으로 잘라서 부분별로 문제를 처리할 수 있도록 합니다. 이때 각 코끼리별로 '이 코끼리부터 사진을 찍을때 구간의 마지막 코끼리까지 찍는데 드는 카메라의 수'와 '그때의 사진이 찍히는 가장 먼 범위'를 구하면 업데이트당 N보다 작은 시간에 문제를 풀 수 있습니다. 처음 1번 코끼리부터 시작해서 해당 구간을 모두 찍는 카메라의 수를 알아낸 뒤, 그만큼의 사진기를 사용할 때 찍히는 범위를 알 수 있으니 다음 구간에서 몇번 코끼리부터 시작을 해야할지를 이진 탐색등으로 알아 낼 수 있습니다. 이런 방식으로 진행하면 코끼리들을 한 마리씩 보지 않고 구간 단위로 넘어가 O(sqrt(N) * lg N) 정도의 시간이 됩니다. 업데이트의 경우 원래 위치의 코끼리를 한마리 없애고 새로운 코끼리를 추가한다고 생각하면 버킷안에서 코끼리를 바꿔 준 후 그 구간 안에서만 새로 값들을 일일히 갱신해주면 됩니다. 결론적으로는 각각 구간의 개수와 구간의 길이에 비례하는 시간이 들게 되어 쿼리마다 O(sqrt(N) * lg N)의 시간으로 문제가 해결됩니다. 하지만 이 풀이를 그대로 제출하면 50점 밖에 받을 수 없습니다. 한 가지 심각한 풀이의 문제점이 있기 때문인데요, 바로 코끼리들이 계속 한 구간으로 옮겨지면 그 구간의 길이가 비정상적으로 커져 더이상 업데이트가 N보다 작지 않은 시간이 걸리게 된다는 점입니다. 이 문제점은 사실 아주 간단하고 참신한 아이디어 하나로 해결됩니다. 바로 쿼리를 sqrt(Q)개 처리 할때마다 버킷들을 완전히 새로 구성하는 것입니다. 이 개수의 쿼리는 처리해도 구간의 길이가 두배 이상 증가하지 않으므로 앞의 문제점이 해결되고, 새로 구성할 때 걸리는 시간도 sqrt(Q)회 정도 밖에 새로 구성을 하지 않고 한번 구성하는데 O(N)의 시간이 소요되므로 점체 시간복잡도에 큰 영향을 주지 않습니다. 이 최적화를 적용하면 100점을 받을 수 있습니다.
Parrots
굉장히 흥미로운 문제였습니다. 서브태스크 별로 하나씩 생각해보면서 풀이를 찾아 보았습니다.
Subtask 1에서는 모든 수가 0 또는 1이고 보낼 수 있는 비트수는 널널하니까 이진수로 바꿔서 하나만 날리면 됩니다
Subtask 2에서는 비트수가 널널하므로 앞의 네자리로 위치를, 나머지 자리로 수를 저장해 보내면 됩니다.
Subtask 3, 4, 5에서는 앞쪽의 위치를 저장할 비트를 분리하면 남는 비트가 255까지 다 저장을 할 수 없습니다. 저는 이 위치 비트를 분리하는 방법을 그대로 응용해서 98점 풀이를 생각을 했는데, 바로 중복 조합을 이용하는 방법입니다. 섭태 5를 기준으로 이야기를 하면 위치비트 제외 총 두 개의 비트를 사용할 수 있습니다. 그 말은 위치별로 총 4개의 신호를 보낼 수 있다는 의미인데, 여기서 각 신호별로 도착한 개수와 0~255까지를 매칭시키면 신호를 다시 숫자로 복호화 할 수 있습니다. 0이 1개, 2, 3이 2개면 57 이런식으로요. 이렇게 0~255와 각 신호의 개수를 모두 매칭 시키기 위해서는 최대 몇개의 신호를 보내야 할지를 중복조합을 이용해 계산해보면 각 자리별로 7개라는 결론이 나옵니다. 이 풀이로는 섭태 5에서 6<P<=7에 해당되어 98점까지 받을 수 있습니다. 100점 풀이는 각 자리별로 대응을 시키는 것이 아니라 모든 자리를 한번에 대응을 시켜주는 방법을 사용하면 받을 수 있다고 합니다. 셋 돌때는 제일 처음 잡은 문제였고 잡은지 1시간 정도에 해결했습니다. 풀이는 굉장히 빠르게 찾았지만 실제 완성까지 조금 시간이 걸렸습니다.