티스토리 뷰

IOI/IOI2014

[IOI2014 Day1] Rail 해법

전명우 2014.07.17 06:12

우선, 이 문제에 대해 본격적으로 설명하기에 앞서 이 문제에서 특성을 몇 가지 설명하겠다.


  1. $d(i,j)$를 정류장 $i$와 정류장 $j$ 사이의 거리라고 할 때, $d(i,j) = d(j,i)$ 이다.
  2. 맨 왼쪽 정류장은 C type 이다.
  3. 맨 오른쪽 정류장은 D type 이다.


$i > 0$인 $i$에 대하여 $d(0,i)$ 를 모두 구한다. 이 때 $d(0,i)$가 최소가 되는 $i$를 $x$라 하자. 이 때 정류장 $x$는 정류장 $0$ 보다 오른쪽에 있으면서 가장 가까운 D type 정류장이다.


만약 $d(0,i) = d(0,x)+d(x,i)$ 라면 정류장 $i$는 정류장 $x$ 보다 왼쪽에 있다. 이 문제를 해결하기 위해, 정류장 $x$를 기준으로 왼쪽에 있는 것과 오른쪽에 있는 것들을 나눠 따로 계산할 것이다.


왼쪽 부분과 오른쪽 부분을 계산하는 방법은 크게 차이가 없으므로, 오른쪽 부분을 구하는 방법에 대해서만 설명하겠다.


이제 정류장 $x$를 포함하여 오른쪽에 있는 정류장들만 존재한다고 생각하고 그것들의 위치와 종류를 구해야한다.

우선 정류장들을 정류장 $0$과의 거리 순서대로 정렬하여 그 순서대로 처리한다.


현재 정류장 $i$의 종류를 구하는 과정 중이라고 생각하자. 정류장 $i$가 C type이기 위한 필요충분조건은 현재까지 구한 D type 정류장 중 $d(0,i) = d(0,j)+d(i,j)$를 만족하는 정류장 $j$가 존재하는 것이다. 여기서, $d(i,j)$를 쿼리로 물어보지 않고 조건을 만족하는지 확인할 수 있다. 마지막으로 구한 D type 정류장을 $k$라고 하자. $d(i,k)$를 쿼리로 물어보고 $d(i,j)=d(i,k)-(L[k]-L[j])$ 라고 가정하여 $d(i,j)$를 매번 물어보지 않아도 된다. (여기서, L은 정류장의 위치를 나타내는 배열). 하나의 위치에 정류장이 하나 밖에 없는 조건 때문에 이러한 가정이 성립한다. 이에 대한 자세한 설명은 생략하겠다.


정류장 $i$의 종류를 결정했다면, 위치를 계산하는 것은 어렵지 않다.


$d(0,i)$를 계산하는 것에서 $N-1$번의 호출을 하고,

$d(x,i)$를 계산하는 것에서 $N-1$번의 호출을 하고,

정류장 $i$의 종류를 결정할 때, $d(i,k)$를 물어보므로, 최대 $N-2$번의 호출을 한다. 따라서, $3(N-1)$번 보다 적게 호출하므로 만점을 받을 수 있다.


시간복잡도는 $O(N^2)$ 이다. 이분 검색을 통하여 $O(N lg N)$에도 해결 가능하다.


코드 보기

저작자 표시
신고

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

[IOI2014 Day2] Gondola 해법  (0) 2014.07.17
IOI2014 Day 2 종료  (0) 2014.07.17
[IOI2014 Day1] Rail 해법  (0) 2014.07.17
[IOI2014 Day1] Game 해법  (1) 2014.07.17
[IOI2014 Day1] Wall 해법  (0) 2014.07.17
IOI2014  (0) 2014.07.17
댓글
댓글쓰기 폼