티스토리 뷰

ICPC/2013 인터넷예선

E. Falling Ants

전명우 2013.09.29 17:19


ProblemE_Eng.pdf


이 문제는 말리면 꽤 시간이 많이 걸릴 듯 해보이는 문제다.

대회 당시에는 나는 문제도 모른채, 팀원이 막힘 없이 풀어주었다.

대회가 끝나고 글을 쓰기 위해 문제를 생각해보았는데, 생각하는데 오래 걸린 편이었다.


이런 개미 문제 컨셉은 BOI? CEOI? 기출 문제에도 있다. 그 문제에서 중요한 점은 "개미의 충돌이 있어도 개미가 떨어지는 시점(시간)은 변함 없다." 이다. 이 문제에서도 꼭 필요한 아이디어다.

추가 설명을 하자면, 개미의 충돌이 있고 두 개미가 서로 방향을 바꿔, 왔던 길을 다시 가더라도 멀리서 봤을 때, 충돌 없이 개미가 서로 지나쳐 가는 것이랑 다를 것이 없다.


하지만 이 문제에서는 떨어지는 개미의 index를 알아야 한다.

필자는 이 문제를 쉽게 생각했다가 말려 시간이 오래걸린 케이스다.


또 하나의 중요한 관찰이 필요하다. 떨어지는 개미의 index는 초기 양 끝점에 있는 개미의 index와 같다.

첫 아이디어와 이 아이디어를 종합하면 이 문제를 해결할 수 있다.

예를 들어 지금 왼쪽에서 개미가 떨어져야 할 차례면, 맨 왼쪽에 있는 개미가 떨어질 것이라는 것이다.

마찬가지로, 지금 오른쪽에서 개미가 떨어져야 할 차례면, 맨 오른쪽에 있는 개미가 떨어질 것이다.

* 개미가 떨어져야 할 차례란, 첫 아이디어를 통해 떨어지는 시간과 방향을 시간 순대로 정렬해서 처리할 때의 차례를 말한다.


처리하기가 까다로운 부분은 문제 설명에서 중요하게 언급된, "동시간 대에 두 개미가 떨어질 경우" 이다.

우선 개미의 좌표는 유일하므로, 동시간 대에 떨어지는 개미는 최대 두 마리임이 자명하다.

이를 이용해 두 개미 중 index가 작은 개미를 먼저 떨어뜨리는 처리를 하면 된다.


E.cpp


'ICPC > 2013 인터넷예선' 카테고리의 다른 글

G. Moore Machine  (0) 2013.09.29
F. KCPC  (0) 2013.09.29
E. Falling Ants  (0) 2013.09.29
D. 이중 우선순위 큐  (0) 2013.09.29
C. Casting  (0) 2013.09.29
B. 카잉 달력  (0) 2013.09.29
댓글
댓글쓰기 폼