Tuesday, October 29, 2013

ACM ICPC 2010 Daejeon Regional - H Installations

Problem Link

우선, 먼저 알 수 있는 사실은 다음 2가지이다.
1) 모든 작업이 끝나기 위해서는 Sum(s1, s2, ... , sn)의 시간이 필요하다.
2) 시간이 t가 흘렀고, 마치지 못한 작업의 마감 시간이 di, dj일 때(t > di, t > dj), di < dj라고 가정을 한다면, di를 먼저하고 dj를 하는 것이 항상 이득이다.
i) i 다음에 j를 할 경우 : (t+si-di) + (t+si+sj-dj) = 2t + 2si + dj - (di+dj)
ii) j 다음에 i를 할 경우 : (t+sj-dj) + (t+sj+si-dj) = 2t + si + 2dj - (di+dj)
따라서 i)의 결과가 ii)의 결과보다 작게 되므로 dk(1<=k<=n)를 시간순으로 정렬한 다음에 작업들을 순차적으로 처리하면 됨을 알 수 있다.

여기서 d(t, i)를 시간 t에 대해서 i번 작업까지 수행했을 때, 최소 비용( minimmum sum of the penalties of the jobs with the two largest penalties)으로 테이블을 정의하여 dynamic programming을 떠올렸었다. 그러면 시간복잡도는 O(T*N)이라서 시간 안에는 충분히 나올 것 같았다. 그런데 생각을 더 하다보니 이 문제의 핵심은 2개의 작업에 대해서만 패널티의 합을 최소화하면 된다는 것이다.

n개의 작업들을 d를 기준으로 오름차순 정렬하였을 때, 일들을 순차적으로 처리해 나가다가 생겨나는 패널티의 최댓값(M1)과 그 다음 최댓값(M2)이 답이 아닐까 생각해보았다. 하지만 이 방법은 첫번째 예제에서부터 틀렸음을 알 수 있다. 위에서 보였던 '2)'는 di와 dj를 비교할 때, i 다음에 곧바로 j를 수행함으로써 성립하는 사실이기 때문이다. 따라서 답이 되는 M1과 M2가 인접하여 생겨나지 않을 경우가 반례인 것이다.

위의 방법으로 나온 M1과 M2가 생성된 위치 중 가장 나중의 위치를 p라고 하자. 지금까지 구한 해보다 더 좋은 해는 p 이하인 지점에서 생성됨을 알 수 있는데 이는 증명을 생략한다.(이 부분 때문에 d가 같다면 s가 내림차순으로 정렬되어야한다.) 1~p번째 작업에 대해서 i번째(1<=i<=p) 작업을 가장 나중에 했을 때, 위의 방법과 마찬가지로 M1과 M2를 구해서 더 좋은 답이 있는지만 검사해주면 되겠다고 생각했고 이 방법으로 AC를 받았다.

명우와 연습을 할 때, 실제 대회와 같은 긴장감 속에서 연습을해서 패널티가 중요했기 때문에 손으로 몇 가지 경우를 해보다가 위의 방법이 반례가 없길래 시도해보았다. 아직 엄밀하게 이 방법을 증명하진 못했지만, 2개의 작업에 대해서만 패널티의 합을 최소화하는 것이라서 가능한 것 같다. 시간복잡도는 O(N^2)이다.

2010년 리저널을 연습할 때, 명우와 2명이서  2시간 30분 동안 긴장감있게 연습하였는데 2시간 동안 7문제를 풀었다. 나머지 3문제는 좀처럼 해결될 기미가 잘 보이지 않았다. 두호형을 포함해서 3명이 같이 했었다면 남은 3시간 동안 1~2문제는 더 풀었을 것 같다. 대회 당시 1등팀이 2시간 반만에 10문제를 모두 해결하였음을 고려하면(2등팀이 8문제이긴 하지만) 아직은  뒷심이 부족하다고 생각된다.

소스 코드 : http://ideone.com/CrKv8U

No comments:

Post a Comment