PS 이야기

문제: 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 점) 수의 비트 수는 ..

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/elephants.pdf대회 당시 이 문제에 상당히 많은 시간을 투자했다. 시간제한이 9초라는 것을 간과하고 단지 N 제한이 크다는 이유 만으로 해법이 $O(N lg N)$ 꼴로 나올 것이라 확신했었다. 부분 점수를 받기 위해 $O(N\sqrt{N})$ 꼴의 방법도 생각해보았지만, 실패했었다.대회 끝나고 나오자마자 당시 조교로 있었던 권순일 형의 짧은 말로 이 문제의 해법을 깨닫게되었다. 2년이 지난 지금까지도 기억에 남는다. 시간복잡도는 $O(N\sqrt{N})$ 이 맞다. 안된다고 생각할 수 있지만, $\sqrt{N}$ 번의 update 마다 새로 그룹들을 $O(N)$만에 구성해주면된다. 그러면 총 시간복잡도를 $O(N\sq..

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/crocodile.pdf우선, 0번 방에서 탈출 방에서 가는 것이 아닌, 탈출방에서 각 방으로 가는 방향으로 뒤집어 생각해야한다. $$D[i] = 악어문지기가\ 최선을\ 다\ 할때,\ 임의의\ 탈출방에서\ i번\ 방으로\ 오는\ 최소\ 시간$$D[i] 를 위와 같이 정의하자. D[i]는 i번 방으로 올 수 있는 방들 중에 D[j]+(j번 방에서 i번 방으로 이동하는 시간)이 2번째로 작은 값을 취해야한다. 이를 해결하기 위해서는 $O(N^2)$ 방법과 $O(N lg N)$ 방법이 존재한다.$O(N lg N)$ 방법은 힙(heap)을 이용해 다잌스트라(Dijkstra's Algorithm)를 돌리듯이 하면 된다.코드: http:/..

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/race.pdf이 문제는 분할정복기법(Divide & Conquer)로 풀 수 있다. 노드 v를 선택하고 v를 포함한 길이가 K인 경로 중 가장 짧은 경로를 찾는다. 그리고 노드 v를 제거한다. 남은 트리들에서 일련의 과정을 반복한다. 분할정복으로 풀기 위해서는 다음 두 사항을 해결해야된다.어떻게 노드 v를 포함한 가장 좋은 경로를 찾을 수 있는가?수행시간을 최적으로 만들 노드 v를 어떻게 찾아야 하는가?우선 노드 v를 포함한 가장 좋은 경로를 찾는 법은 꽤 간단하다. 노드 v를 루트로 한 트리를 만들고 dfs를 돌리면 길이가 K이면서 가장 짧은 경로를 O(N)만에 찾을 수 있다. dfs를 돌릴 때 크기가 K인 배열을 이용해야한..

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/garden.pdf 대회 때, 문제가 너무 어려워 보여 별다른 도전을 하지 못한 채 49점을 받았다. 최근에 문제를 다시 풀어보았을 때, 노가다 문제임을 알 수 있었고, 까다로운 코딩 끝에 만점을 받을 수 있었다. 대회 때 문제를 풀지 못한 것에 대한 아쉬움이 커졌다. 이 문제는 69점을 받는 방법이 딱히 생각 나지 않는다. 다만, 코딩할 때 배열 대신 vector를 썼을 때 시간초과로 69점을 받게 됬다. vector를 배열로 고치니 넉넉하게 만점이 나왔다. 대회 때 69점 받은 사람이 상당히 많은데, 69점을 받기 위한 쉬운 방법이 있는지 잘 모르겠다. 문제의 해법에 접근하게 위해서 몇 가지 관찰이 필요하다.어떤 노드 i에서..

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/ricehub.pdf이 문제를 풀기 위해서, 어떤 구간이 있을 때, 그 구간에 있는 논들의 쌀을 다 가져오기 위한 최소 비용을 계산할 수 있어야한다. 구간 (i,j)가 있다는 것은 구간에 속한 논이 X[i], X[i+1], ..., X[j]라는 것이다. 이 때, 쌀창고는 X[(i+j)/2]에 놓는 것이 비용을 최소화 할 수 있다. 따라서, 구간 (i,j)에 대해 최소 비용을 O(N)의 전처리가 되어 있으면, O(1) 만에 구할 수 있다.이제 답은 최소 비용이 B를 넘지 않은 최대 구간 크기와 같다. 이를 O(N)만에 구할 수 있다. i=0, j=0에서 시작하여, i를 계속 증가 시켜가면서 구간 (j,i)의 최소 비용이 B를 넘으..