PS 이야기

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