PS 이야기

우선, 이 문제에 대해 본격적으로 설명하기에 앞서 이 문제에서 특성을 몇 가지 설명하겠다. $d(i,j)$를 정류장 $i$와 정류장 $j$ 사이의 거리라고 할 때, $d(i,j) = d(j,i)$ 이다.맨 왼쪽 정류장은 C type 이다.맨 오른쪽 정류장은 D type 이다. $i > 0$인 $i$에 대하여 $d(0,i)$ 를 모두 구한다. 이 때 $d(0,i)$가 최소가 되는 $i$를 $x$라 하자. 이 때 정류장 $x$는 정류장 $0$ 보다 오른쪽에 있으면서 가장 가까운 D type 정류장이다. 만약 $d(0,i) = d(0,x)+d(x,i)$ 라면 정류장 $i$는 정류장 $x$ 보다 왼쪽에 있다. 이 문제를 해결하기 위해, 정류장 $x$를 기준으로 왼쪽에 있는 것과 오른쪽에 있는 것들을 나눠 따로 ..

여러 가지 다양한 해법이 있다고 생각한다. $0$번 도시 부터 $N-1$번 도시까지 총 $N$개의 도시가 있다. 이 $N$개의 도시들을 단말 노드로 갖는 이진 트리를 만든다. 이 이진트리의 단말 노드의 개수는 정확히 $N$개이다. 이제 모든 $(i,j)$ 쌍 ($0 \leq i < j \leq N-1$)에 대하여 단말 노드 $i$와 단말 노드 $j$의 LCA(Lowest Common Ancestor, 최저 공통 조상)를 $k$라 했을 때, left[k]에 1을 더한다. 쿼리(질문)가 $(u,v)$으로 주어졌을 때, 단말 노드 $u$와 단말 노드 $v$의 LCA를 $w$라 했을 때, left[w] 값을 1 감소 시키고, 그 값이 0 이면, 값을 1 반환하고 감소한 뒤 그 값이 여전히 0 보다 크다면 0을 ..

Segment Tree를 이용하여 해결하는 문제다. Segment Tree의 각 노드별로 구간 내에서 최소값과 최대값을 가지고 있는다. add 연산은 lower boundary(최소값)을 변화시키고, remove 연산은 upper boundary(최대값)을 변화시킨다. Segment Tree를 순회할 때 자신(현재 탐색 중인 노드)의 조상에 대한 값을 자신한테 반영할 수 있도록 신경쓴다. 각 노드의 값 갱신에 대해 자세한 설명은 생략한다. 첨부된 소스를 참고하길 바란다. $K$개의 쿼리마다 계산하는 시간복잡도는 $O(lg N)$이며, 최종적으로 각 위치에 대한 높이를 계산하는 시간복잡도는 $O(N)$이다. 그러므로 총 문제를 해결하는 시간복잡도는 $O(K lg N + N)$이다. #include #inc..

지금 IOI2014 대회가 한창 진행 중이다. Contest Day 1은 어제 진행 되었으며, Contest Day 2는 내일 진행된다. 개최국은 대만이며, 우리나라와 시차가 1시간 밖에 안된다. 시험은 내일 우리나라 시간으로 아침 10시부터 오후 3시까지 5시간 동안 진행된다. 문제는 아직 공식적으로 공개된바 없으며, 구글링을 해본 결과 http://math.mit.edu/~rpeng/IOI2014/ 에서 영문판, 중국어판 문제를 볼 수 있다. Live Scoreboard는 http://live.ioi2014.org/Ranking.html 에서 볼 수 있다. 한국 대표 최석환, 조승현, 윤지학, 이창수 군 모두 좋은 성적 받고 기쁜 마음으로 귀국할 수 있길 바란다. Day 1 문제 셋은 3개의 문제로 ..

문제: 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를 넘으..