ACM ICPC Asia Regional - Seoul 2006

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=249

좀 많이 입풀이라... 가려 듣길 부탁한다 ㅠㅠ

D : Travel

검증되지 않은 풀이다.

제대로 읽었다면 s - t, u - v를 잇는 vertex-disjoint path를 찾는 문제로, maximum flow를 짰고 틀렸다. 데이터탓이라고 정신승리후 끝냄.

E : Roommate

옛날에 AC했었다. 풀이는 대충... 이랬던거 같다.

dp[i][j][t1][t2] -> 지성(0번)이 i번 task까지 "완벽히" 완료했으며, 영표(1번)가 j번 task까지 "완벽히" 완료했고, t1번째 사람이 i+1 / j+1번째 task를 t2 시간동안 돌렸다.

점화관계를 O(1)에 유도할 수 있다. 좀 더러우니 잘 짜야한다.

여담으로 내 알고리즘보다 빠른 그리디 알고리즘이 존재한다. 최단 경로 문제로 귀결가능하다고.

F : Gas

M(x) = f(x)의 합이라고 할 때 M(x)가 x에 대한 증가함수이기 때문에, 주어진 값을 만족하는지 이진탐색으로 쉽게 구할 수 있다. lower_bound 짜듯이 하면 된다.

G : Tree

???

H : Period

검증되지 않은 풀이다.

X의 [0, i-1] 구간 substring에 대해서, 최소 k는 dp[i] = (j < i) Min(max(dp[j], EditDistance(X[j, i-1] , Y)) 라는 점화식으로 계산할 수 있다. 이 알고리즘을 그냥 구현하면 TLE가 난다.

관찰할 수 있는 점은 dp[N]은 커봐야 |Y|+1이라는 점이다. 모든 구간을 1으로 쪼개면, EditDistance(X[i, i], Y)가 |Y|+1 이상이 될 수 없기 때문이다. 이는 또 한 가지 최적화를 가능케 하는데, X를 쪼개는 각각의 구간은 길어봐야 2|Y| + 1 라는 점이다. (그 이상일 경우 delete만 해도 |Y|+1이 벌써 넘어간다.)

이제, X의 모든 2|Y|+1 길이의 substring에 대해서 edit distance를 O(|X||Y|^2)에 precalc한 후, dp를 O(|X||Y|)에 계산하면 풀 수 있다.

I : Fire Tower

검증되지 않은 풀이다.

주어지는 polygonal chain들은 탑을 세울 수 있는 영역을 제한시키는 반평면으로 해석할 수 있다. 이러한 반평면들의 교집합은 볼록한 형태(convex polygonal chain)를 이루고, 만약 그러한 형태를 구할 수 있으면 탑을 세울 수 있는 후보지역은 많아야 2N개임을 알 수 있다.

이제 교집합을 구하는 것이 문제인데, 다양한 방법이 있지만 convex hull trick이 가장 편하다고 생각.

J : Log Jumping

제약된 형태의 interval graph (= unit interval graph)에서의 hamilton cycle을 구하는 문제이다.

직관적인 아이디어는 가장 좌측에 있는 점 -> 가장 우측에 있는 점을 잇는 두개의 disjoint하며, 모든 점을 덮는 path를 찾는 방법이다. 그리디로 해결이 가능한데, 끝점 순으로 정렬한 후, 두개의 path를 관리하는데 현재 시작점이 작은 path에 끝점 순으로 붙여나가는 방식이다.

위 그리디를 더 간단하게 바꿀 수도 있다. 끝점 순으로 정렬 후 인덱스를 매기면, 다음을 만족하는 것과 hamilton path가 있다는 점이 동치이다.

 * 1번 정점과 2번 정점이 연결, n-1번 정점과 n번 정점이 연결

 * 1 <= i <= n-2에 대해 i번 정점과 i+2번 정점이 연결.