티스토리 뷰

카자흐스탄 알마티에서 열리는 IOI 2015가 오늘 개막했다.

이전 IOI와 다르게 이번 IOI는 한국대표단에 조교로 소속되어 학생들과 같이 현장에 왔다.


출국 전 3주 동안 합숙 훈련을 마친 학생들에게 좋은 성적을 기대해본다.


원래 연습 세션 문제는 풀이를 적지 않지만, 문제가 상당히 괜찮아보여 처음으로 적어보려한다.

관련 자료들은 여기에서 다운받을 수 있다.


1. search


문제: search.pdf


정렬되어 있는 배열이 입력으로 들어오므로 이분 검색을 통해 위치를 구하면 되는 아주 쉬운 문제다. 배열의 크기가 최대 100번이므로 7번의 질문으로 위치를 구할 수 있다.


코드 보기


2. divide


문제: divide.pdf


"S[i] = 1 번째 수 부터 i 번째 수 까지 XOR 한 값" 으로 배열 S를 정의하자.

j+1 번째 수 부터 i 번째 수 까지 XOR 한 값은 S[i] $\oplus$ S[j]가 된다.

"D[i] = 처음부터 i번째 수 까지만 있다고 가정했을 때 나눌 수 있는 구간의 최대 개수" 으로 DP배열을 정의하자.

점화식은 다음과 같다. D[i] = max(D[j] + 1) (단, 0 ≤ j < i이며 S[i] $\oplus$ S[j] ≤ M, D[0] = 0, S[0] = 0)

기본적으로 위 알고리즘은 $O(N^2)$의 시간복잡도를 갖는다.


문제에서 주어지는 수의 비트 수를 $X$라 하자. 

어떤 i에 대해 S[i] $\oplus$ S[j] ≤ M을 만족하는 j 들을 찾기 위해 우리는 수들을 이진수로 나타내고 가능한 S[j]의 binary prefix에 대해 최대값을 빠르게 탐색, 기록하기 위해 trie 구조를 사용한다.

예를 들어, S[i] = $110110_{(2)}$, M = $100010_{(2)}$라고 했을 때, 고려해야되는 prefix는 $1?????_{(2)}$, $01011?_{(2)}$, $010100_{(2)}$ 세 가지가 된다. 즉, '?' 자리에는 아무 수나 올 수 있고 저런 패턴을 가진 S[j]만이 S[i] $\oplus$ S[j] ≤ M가 된다. 이러한 패턴은 최대 X개 있을 수 있다.

총 시간복잡도는 $O(NX)$가 된다.


코드 보기


3. graph


문제: graph.pdf


준비 중.


코드 보기


저작자 표시
신고

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

IOI 2015 Day 2 문제 및 해법  (2) 2015.07.30
IOI 2015 Day 1 문제 및 해법  (0) 2015.07.28
IOI2015 개막 . 연습 세션 문제 설명  (0) 2015.07.28
댓글
댓글쓰기 폼