티스토리 뷰

IOI/IOI2015

IOI 2015 Day 1 문제 및 해법

전명우 2015. 7. 28. 12:23

0. 표지


notice_en-KOR_rev17.pdf


1. boxes


문제: task-1_en-KOR_rev47.pdf


최적의 이동 방법이 있다고 하자. 이 이동 방법에서는 절대 반시계방향으로 이동한 경로와 시계방향으로 이동한 경로가 교차하는 일은 없다. 이 때 경로라 함은 선물을 주러 이동하는 경로만을 얘기하며 선물을 다시 가지러 0번 지점으로 이동한 경로는 제외하고 말했다. 그렇기 때문에 문제에서 원형의 일부를 끊어 선형으로 바꾸어 생각할 수 있다. 선형으로 바꾼 경우, 0번 지점을 기준으로 음수 좌표와 양수 좌표를 나누어 생각할 수 있다.

결국 선형인 경우에 대해 욕심쟁이 기법으로 답을 전부 구해놓은 뒤, 모든 지점에 대해 끊어 선형으로 바꾼 뒤 답을 계산하면 된다.

선형일 때 주의해야할 점은 K개의 지점에 선물을 나누어주고 다시 0번 지점으로 돌아가는 경로는 원형에서 이루어지는게 최적일 수 있다는 것이다.

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



2. scales


문제: task-2_en-KOR_rev136.pdf


처음에는 답으로 가능한 후보가 $6! = 720$가지가 있다. 이 상황에서 임의의 질문을 하고 나올 수 있는 대답은 3가지이다. 대답에 따라서 답으로 가능한 후보 집합이 줄어들게 된다.

현재 상황에서 제일 좋은 질문은 나올 수 있는 3가지 답변에 대해 최악의 경우(후보 집합이 별로 안줄어드는 경우)가 제일 좋은 질문이다. 따라서 현재 후보 집합이 있을 때, 각 질문 별로 최악의 경우를 계산하고, 제일 좋은 질문을 찾아 그 질문을 한다. 질문의 답변이 무엇이냐에 따라 후보 집합이 바뀌게 되며, 이렇게 바뀐 후보 집합의 크기가 1이 될 때 까지 재귀적으로 생각하면 된다.

질문은 총 120가지가 있을 수 있으며, 답으로 가능한 경우는 720가지 경우이다. 모든 순열에 대해 모든 질문에 대한 답변을 미리 계산해둘 수 있으므로, 이 문제는 시간안에 해결할 수 있다.

이런 식으로 질문을 하면 가능한 720가지 입력에 대해 최대 7번의 질문으로 순열을 판단할 수 있다. (71점짜리 풀이다.)



하지만 6번의 질문으로 모든 순열을 판단할 수 있다. 위의 방법에서 문제가 되는 부분은 최악이 제일 좋은 경우가 여러 가지인 경우 그 다음에 발생하는 최악이 제일 좋은 질문을 해야 최적의 질문을 할 수 있다. 바로 다음 상황 뿐만아니라 그 이후 상황들에 대해서도 고려하면 최대 6번의 질문으로 순열을 판단할 수 있다. 이에 대한 빠른 구현 방법은 아래 코드를 참고하자. 아래 코드는 테스트케이스가 720가지인 경우에 대해서도 1초안에 문제를 해결한다.



3. teams


문제: task-3_en-KOR_rev53.pdf


각 날에 대해서 욕심쟁이 기법이 가능하다. 요구하는 팀의 크기가 작은 프로젝트부터 처리를 하는데, 그 프로젝트에 참가할 수 있는 학생이 여러명 있는 경우, 학생의 $B$ 값(팀의 크기 상한)이 작은 학생들을 우선적으로 프로젝트에 투입하면 된다. 이를 우선순위큐, 세그먼트 트리 등으로 구현하면 $O(QN \lg N)$이 나오며, 34점을 받을 수 있다.

우선순위 큐로 구현하는 것은 개선할 여지가 없으므로 세그먼트 트리 동작에 대해 설명하겠다.

우선, 세그먼트 트리로 아래의 4가지 연산을 처리하는 자료구조(집합이라 보자)를 구현하면 된다.

1) 추가. 집합에 $B_i$를 추가한다.

2) 삭제. $B_i \leq x$인 $B_i$들을 집합에서 제거한다.

3) 삭제. 집합에서 값이 제일 작은 $k$개를 제거한다.

4) 크기. 집합에 있는 원소의 개수를 구한다.

1, 2, 3번 연산은 $O(\lg N)$ 시간안에 구현이 가능하며, 4번 연산은 $O(1)$ 시간안에 해결할 수 있으므로, 쿼리별로 시간복잡도는 $O(N \lg N)$이 된다.


만점을 받기 위해서는 전체 시간복잡도가 $O(S \lg N)$ 또는 $O(S {\lg}^2 N)$이 되어야한다. 개선을 해야하는 부분은 1번 연산이다. 각 쿼리마다 최대 $N$번 추가연산을 하는 기존 방법을 계선하기 위해서 추가를 $B_i$하나에 대해서만 할 것이 아니라 여러 개의 $B_i$에 대해 해야한다. 연속적으로 추가되는 $B_i$들이 시작점($A$) 순서대로 학생들을 정렬했을 때 연속적으로 나타나는 부분과 같으므로, 세그먼트 트리 각 노드별로 구간에 속한 시작점들을 정렬해서 가지고 있는다. 그리고 여러 개의 추가 연산은 정렬된 배열에서 pivot을 변화 시키는 과정으로 $O({\lg}^2 N)$에 해결 가능하다. ${\lg}^2$이 되는 까닭은 다음 pivot을 찾기 위해 이분 검색을 해야하기 때문이다.


아마도 77점 풀이는 $O(S {\lg}^3N)$ 풀이이거나 $\sqrt{N}$ 꼴로 나타나는 풀이인 것으로 여겨진다. $O(S {\lg}^2 N)$ 풀이는 대회 때 만점이 나온다.



3-1. teams (2D range query)


문제: task-3_en-KOR_rev53.pdf


마찬가지로 각 날에 대해 욕심쟁이 기법이 가능하다. 이와 관련된 아이디어는 위에서 설명한 것과 같다. 이를 2D range query를 이용해서 해결할 수가 있다. 2D range query란 2차원 상에 점이 $N$개가 있을 때, 어떤 임의의 직사각형 영역(물론, 좌표축과 변이 평행한)에 있는 점의 개수를 $O({\lg}^2 N)$에 구하는 방법이다. 이는 일반적인 세그먼트 트리로 구현이 가능하며, $x$ 좌표에 대한 세그먼트 트리의 각 노드에 그 $x$ 좌표 구간에 포함된 점들의 $y$ 좌표들을 정렬해서 저장해두고, 쿼리 때마다 이분 검색을 통해 구간에 대한 개수를 구할 수 있다.


학생을 점 하나로 표현한다. $i$번 학생의 x 좌표는 $B_i$가 되고, y 좌표는 $A_i$가 된다. 필요한 팀의 크기가 $s$인 프로젝트에 참여할 수 있는 학생은 $(s, s)$ 의 $x$ 좌표는 $s$이상이며 $y$좌표는 $s$ 이하이므로 참여할 수 있는 학생의 수를 셀 때 직사각형 영역에 있는 점의 개수를 구하면 된다. 마찬가지로 여기서 문제는 이미 다른 프로젝트에 참여한 학생들을 제외하고 세어주어야한다는 것인데, 이는 스택(가변 크기 최대 $M$)을 이용해서 이미 프로젝트에 참여한 학생들이 있는 영역을 제외한 나머지 직사각형 영역에 대해 포함된 점의 개수를 구하면 된다. 이는 아래 그림을 참고하자.




색칠된 초록색 영역과 파란색 영역에 속한 학생들이 이미 다른 프로젝트에 참여하게 되었다면, 위 처럼 세 영역에 대해서 포함된 점의 개수를 세어주면 된다. 1번 영역에서 학생의 수가 부족하다면, 2번 영역에서 학생의 수를 세어주는데 이 때, 파란색 영역에 관련된 정보는 스택에서 pop 된다. 따라서 쿼리별로 시간복잡도는 $O(M {\lg}^2 N)$이므로 전체 시간복잡도는 $O(S {\lg}^2 N + N \lg N)$이 된다. 2D range query를 위한 세그먼트 트리의 전처리 시간복잡도가 $O(N \lg N)$이다.

+ Persistent Segment Tree를 이용하면 2D range query를 $O(\lg N)$에 해결할 수 있다.


코딩할 때 주의해야할 점은 같은 $x$ 좌표를 가지는 점들이 있을 수 있는데, 이런 경우가 있으면 처리가 까다로울 수 있다. 따라서 학생들의 $x$ 좌표를 서로 다르게 만들어야한다.



저작자표시

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

IOI 2015 Day 2 문제 및 해법  (2) 2015.07.30
IOI2015 개막 . 연습 세션 문제 설명  (0) 2015.07.28
공유하기 링크
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2024/11   »
일 월 화 수 목 금 토
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
글 보관함