티스토리 뷰

IOI/IOI2011

[IOI2011 Day1] Garden 해법

전명우 2013.07.23 03:23

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/garden.pdf

대회 때, 문제가 너무 어려워 보여 별다른 도전을 하지 못한 채 49점을 받았다. 최근에 문제를 다시 풀어보았을 때, 노가다 문제임을 알 수 있었고, 까다로운 코딩 끝에 만점을 받을 수 있었다. 대회 때 문제를 풀지 못한 것에 대한 아쉬움이 커졌다.

이 문제는 69점을 받는 방법이 딱히 생각 나지 않는다. 다만, 코딩할 때 배열 대신 vector를 썼을 때 시간초과로 69점을 받게 됬다. vector를 배열로 고치니 넉넉하게 만점이 나왔다. 대회 때 69점 받은 사람이 상당히 많은데, 69점을 받기 위한 쉬운 방법이 있는지 잘 모르겠다.

문제의 해법에 접근하게 위해서 몇 가지 관찰이 필요하다.

  • 어떤 노드 i에서 시작했을 때, 생기는 경로는 유일하다.
  • 어떤 노드 i에서 시작했을 때, 생기는 경로의 꼬리 부분에 싸이클이 존재한다.
  • 어떤 노드 i에서 발생할 수 있는 상황은 2가지이다.
    1. 가장 아름다운 산책로를 이용할 수 있는 경우
    2. 두번째로 아름다운 산책로를 선택할 수 밖에 없는 경우

이런 관찰들로 어떤 노드 i에서 1번 경우일 때와 2번 경우 일 때 경로가 어떻게 구성되는지를 DFS 로 구해 놓으면 된다. 각 경로에 도착지인 P가 어디에 위치하는지 저장해놓으면 된다. 다만 경로에서 P가 여러 곳에 위치할 수 있음을 간과해서는 안된다. 이를 간과하지 않으면 직관적이게 해결할 수 있다. 쿼리별로 시간복잡도 $O(N)$만에 해결할 수 있다.

총 시간복잡도는 $O(QN)$ 이다.

이 문제의 해법을 생각하기는 매우 쉽다. 다만 예외의 경우가 몇 가지 있어, 코딩할 때 실수하기 쉬워 어렵다.

코드 보기


댓글로 한 분이 69점 받을 수 있는 방법을 알려주셨다. 그 방법을 자세히 소개하겠다.

우선 쿼리별로 시간복잡도가 $O(N lg K)$ 이기 때문에 100점이 아닌 69점이 나온다. 각 노드 별로 1번 이동한 후, 2번 이동한 후, 4번 이동한 후, ..., $2^i$번 이동한 후 도착지를 계산해놓으면 된다. 미리 계산하는 시간복잡도 또한 $O(N lg K)$ 이다. 계산할 때 노드에 도착하고 다음 이동 할 때, 가장 아름다운 도로로 이동하게 될 수도 있고, 두 번째 아름다운 도로로 이동하게 될 수도 있음을 주의해야한다.

총 시간복잡도는 $O(Q\bullet N lg K)$ 이다.

신고

'IOI > IOI2011' 카테고리의 다른 글

[IOI2011 Day2] Parrots 문제 고찰 및 해법  (1) 2013.07.24
[IOI2011 Day2] Elephants 해법  (0) 2013.07.24
[IOI2011 Day2] Crocodile 해법  (0) 2013.07.24
[IOI2011 Day1] Race 해법  (4) 2013.07.23
[IOI2011 Day1] Garden 해법  (3) 2013.07.23
[IOI2011 Day1] Ricehub 해법  (0) 2013.07.23
댓글
댓글쓰기 폼