티스토리 뷰

IOI/IOI2015

IOI 2015 Day 2 문제 및 해법

전명우 2015.07.30 12:05

0. 표지


notice_en-KOR_rev27.pdf


1. horses


문제: task-1_en-KOR_rev68.pdf


말을 한 번 팔 때, 모두 팔아버리는 것이 좋음을 알 수 있다. $i$번 해에 말을 파는게 제일 좋기 위한 필요조건은 $i < j$인 모든 $j$에 대해 $Y[i] \geq X[i+1] \times \dots \times X[j] \times Y[j]$ 를 만족해야한다. 여기서 주목해야할 점은 $Y[i] \leq 10^9$라는 것이다. $X[i] > 1$인 $i$들 중 30개 보다 앞에 있는 날에 말을 파는 것은 안좋다는 것을 알 수 있다. 결국 답으로 가능한 구간이 최대 30개 생기는 꼴인데 매 쿼리마다 각 구간 별로 최대 $Y[i]$를 인덱스트리나 세그먼트 트리로 구해놓은 다음에 말을 팔고 남은 최대 이익을 계산하면 된다. 그러면 하나의 쿼리를 $30 \lg N$ 에 조금 비례한 회수의 연산으로 해결할 수 있다.


코드 보기


2. sorting


문제: task-2_en-KOR_rev80.pdf


우선 가장 먼저 파라매트릭 서치를 생각할 수 있다. $R$ 라운드 이내에 정렬이 가능하다고 가정하고 답이 되는지 확인한다. 파라매트릭 서치가 되는 이유는 $R$ 라운드에 정렬이 가능하면 $R+1, R+2, \dots, M$ 라운드에도 항상 정렬이 가능하기 때문이다. $R$ 라운드에 정렬이 완료되고 나서 이후 라운드에서는 에르맥이 스왑한 것만 따라 스왑하면 항상 정렬 상태를 유지할 수 있기 때문이다.


파라매트릭 서치로 $R$을 정했을 때, $R$ 라운드에 답이 되는지 확인하는 방법을 설명하겠다. 기본적인 아이디어는 아이잔이 앞으로 수열을 전혀 안건드렸을 때, 오직 에르맥의 스왑으로 각 수들이 어느 위치로 가는지 계산한다. 그러면 아이잔은 에르맥의 움직임에 맞춰 최후에 정렬되도록 적절히 스왑해주면 된다.


예제 1번의 경우를 예로 들겠다. $R = 3$일 때 가능한지 확인한다.


에르맥

(0, 1)

에르맥의 이동 경로: 0 3 1 2 4

 수열: 3 4 2 1 0

아이잔

(1, 0)

에르맥의 이동 경로: 0 3 1 2 4

아이잔 수열: 4 3 2 1 0

에르맥

(1, 2)

에르맥의 이동 경로: 0 1 3 2 4

아이잔 수열: 4 2 3 1 0

아이잔

(0, 4)

에르맥의 이동 경로: 0 1 3 2 4

아이잔 수열: 0 2 3 1 4

에르맥

(2, 3)

에르맥의 이동 경로:  0 1 2 3 4

아이잔 수열: 0 2 1 3 4

아이잔

(1, 2)

에르맥의 이동 경로: 0 1 2 3 4

아이잔 수열: 0 1 2 3 4


위 표에서 에르맥의 이동 경로가 0 3 1 2 4라 함은 아이잔 수열에서 0번 위치에 있는 수가 아이잔이 가만히 있는다고 했을 때 0의 위치로 가고 1번 위치에 있는 수가 3번 위치에, 2번 위치에 있는수가 1번 위치에, 3번 위치에 있는 2번 위치에, 4번 위치에 있는 수가 4번 위치에 간다는 뜻이다. 이후 정렬되어 있으면 $R$ 라운드 안에 마침이 가능하다는 것이고, 아니라면, 불가능하다는 것이다. 방법을 보면 에르맥의 스왑 정보와 상관 없이 적어도 $N-1$ 라운드 안에는 끝남이 보장된다. 시간복잡도는 $O(N \lg N)$이다.


코드 보기


3. towns


문제: task-3_en-KOR_rev87.pdf


0번 도시에서 제일 먼 도시를 찾는다. 그 도시의 번호가 $X$번이라 하자. $X$번 도시에 대해 제일 먼 도시를 찾는다. 그 도시의 번호가 $Y$번이라 하자. 트리의 지름이 $dist(X, Y)$임을 알 수 있다. 지금까지 질의 회수는 $2N - 3$ 이다.


여러 가지 증명이 필요한 명제들이 있다. 글에서 증명은 생략하겠다.

1) 트리의 지름이 여러가지일 수 있다. 그러나 허브는 임의의 한 지름의 위에만 존재한다.

2) 허브는 최대 2개다.

3) 1번에서 더 확장하여 허브는 0번 도시와 X번 도시 사이의 경로 위에만 존재한다. (즉, 아래 그림에서 빨간색 대도시는 허브가 될 수 없다.)

$dist(0, i)$와 $dist(X, i)$를 이용해서 $i$번 도시에서 0번 도시에서 $X$번 도시로 가는 경로 상에 위치한 가장 가까운 대도시와의 거리를 구할 수 있다. (그림에서 파란색 가상 간선의 길이) 마찬가지로 $X$번 도시에서 경로 상에 위치한 대도시 와의 거리들(그림에서 초록색 선에 해당)도 구할 수 있다. 이 정보로 경로상에 위치한 대도시의 개수, 허브, 그리고 $R$ 값을 알 수 있다. 이 때 추가 질의 회수는 없다.


구한 허브에 대해서 그 허브가 균형 잡힌 허브인지 확인하는 것이 까다롭다. 그림에서 검정색 대도시들 중 허브가 있을 텐데, 허브에 딸린 파란색 도시들의 개수가 $\frac{N}{2}$ 보다 많다면, 추가적으로 질의를 하여 $\frac{N}{2}$ 보다 큰 파란색 도시 그룹이 나오는지 확인을 해주어야한다. 위에서 말한대로 최대 2개의 허브가 있을 수 있는데, 이러한 추가 확인 작업은 최대 한 개의 허브에 대해서만 해주면 된다. 그 이유는 파란색 도시들을 $\frac{N}{2}$개 보다 많게 가지고 있는 허브는 최대 한 개이기 때문이다.


추가 확인 작업은 $n$개의 원소가 있고, 원소끼리 비교하는 질의만 가능할 때 같은 값을 가지는 원소의 개수가 $\frac{n}{2}$ 보다 많이 있는지, 있다면 몇 개인지 계산하는 문제로 바꾸어 풀 수 있다. 최대 $\frac{3}{2} n$질의 만에 할 수 있다. Majority Vote Algorithm 포스트에 자세히 적혀있다.


코드 보기



저작자 표시
신고

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

IOI 2015 Day 2 문제 및 해법  (2) 2015.07.30
IOI 2015 Day 1 문제 및 해법  (0) 2015.07.28
IOI2015 개막 . 연습 세션 문제 설명  (0) 2015.07.28
댓글
  • 프로필사진 ntopia 안녕하세요...
    1번 코드에서 81번째 줄에
    if (X[i])
    요 코드가 쓰인 특별한 이유가 있나요?
    아님 if (X[i] > 1) 의 오타인가요?
    2015.12.01 19:24 신고
  • 프로필사진 전명우 문제를 읽어보니,
    x[i] 값이 항상 1이상 10^9이하라 딱히 의미가 없는 if 문 같습니다...
    2016.02.10 19:00 신고
댓글쓰기 폼