티스토리 뷰

IOI/IOI2018

IOI 2018 Day 1 문제 및 해법

전명우 2018. 9. 5. 11:14

문제: 공식 홈페이지

채점: Yandex

1. combo


길이가 N인 'A', 'B', 'X', 'Y'로만 이루어진 문자열 S가 있다. 문자열 S의 첫 글자로 나타나는 알파뱃은 오직 한 번만 등장한다. press(p)라는 함수를 문제에서 제공하는데, press(p)에서 p는 길이가 4N 이하인 문자열이며, p의 부분문자열 중 문자열 S의 prefix 중 하나와 동일하며 가장 긴 문자열의 길이를 반환한다. 문제는 적은 횟수의 press(p) 함수 호출을 통해 문자열 S의 내용을 정확하게 알아내는 것이다.


여담으로, p의 부분문자열 중 문자열 S의 prefix 중 하나와 동일하며 가장 긴 문자열의 길이란, 즉, 문자열 S를 패턴이라고 생각하고 p를 전체 문자열이라고 생각했을 때, KMP 알고리즘의 실패 함수 값 중 최대값을 의미한다.


이 문제에서 풀이가 존재하는 이유이며, 가장 중요한 조건은 문자열 S의 첫 문자는 오직 한 번만 등장한다는 것이다. 우선, 첫 글자 후보는 네 종류이며 이분탐색 하듯이 2번의 질문을 통해 첫 글자가 무엇인지 알아낼 수 있다. 첫 글자를 알아내고 나면 뒤에 나오는 문자 후보는 세 종류로 줄어든다. 만약, 첫 글자가 'B'라고 한다면, 이후 등장하는 문자 후보는 'A', 'X', 'Y' 세 종류로 줄어든다.


이후 2이상 N미만인 i에 대해 문자열 S의 i번째 문자를 왼쪽에서부터 차례대로 알아가는데 각 글자를 알아내는 것이 한 번의 질문으로 가능하다. 예를 들어, S의 길이 N이 3이상이고 S의 첫 글자가 'X'라고 하자. press("XAAXABXAYXB")를 질문했을 때, 만약 S의 2번째 글자가 'A'라면 함수 반환 값은 3이 될 것이며, S의 2번째 글자가 'B'라면 함수 반환 값은 2가 될 것이며, S의 2번째 글자가 'Y'라면 함수 반환 값은 1이 될 것이다. 즉, press 함수 반환 값에 따라 S의 2번째 글자가 결정된다. 이런 식으로 질문하면 N-1번째 문자까지 전부 알아낼 수 있다.


마지막 글자도 첫 글자와 마찬가지로 2번의 질문을 통해 알아낼 수 있다. 그러면 여태까지 총 질문한 횟수는 2 + (N-2) + 2 = N+2가 된다. 정리하자면, N=1일 경우 2번의 질문만 하고, 그렇지 않을 경우 N+2번의 질문을 통해 문자열 S의 내용을 정확히 알아낼 수 있다.



2. seats


높이 H, 너비 W, 크기 K=H×W의 격자판이 주어진다. 각 칸에는 0부터 K-1까지 번호가 서로 다르게 쓰여있다. 격자판에서 부분직사각형 영역에 번호가 0부터 차례대로 모두 존재한다면 부분직사각형 영역을 아름답다고 한다. 초기 격자판의 상태와, 특정 두 칸에 적힌 수를 서로 바꾸는 쿼리 Q개가 주어졌을 때, 차례대로 쿼리를 수행하면서 수를 서로 바꾼 직후마다 아름다운 부분직사각형 영역의 수를 구하는 문제다.


쿼리가 없다고 했을 때, 즉, 한 번만 아름다운 부분직사각형 영역의 수를 구하는 방법은 여러 가지다. 여러 방법 중 100점 풀이로 가는 방법은 별로 없다. 0번이 적힌 격자칸부터 번호 순서대로 격자칸을 색칠해나간다고 했을 때, 색칠된 모든 부분이 직사각형을 이룬다면 그 직사각형은 아름다운 부분직사각형 영역이 된다. 색칠해나가는 중간과정을 생각하면서 아래 그림을 보자.



맨 왼쪽 그림의 검은 격자칸은 상, 좌, 상좌대각선이 아직 색칠되어있지 않아서 색칠된 영역이 직사각형을 이룬다면 직사각형의 왼쪽-위 꼭지점이 될 것이다. 마찬가지로 이어지는 그림들도 오른쪽-위 꼭지점, 왼쪽-아래 꼭지점, 오른쪽-아래 꼭지점이 될 것이다. 각 꼭지점이 될 가능성이 있는 검정색 칸의 개수를 세고 더 했을 때 4개가 된다면 직사각형 영역이 될 가능성이 있다는 것이다. 이어서 다음 그림을 보자.



그림처럼 구멍이 존재하면 꼭지점 후보가 4개가 있다고 하더라도 색칠된 칸들은 채워진 직사각형 영역을 이루지 않는다. 1번 칸은 구멍의 왼쪽-위 꼭지점이 될 가능성이 있고, 2, 3, 4번 칸은 각각 구멍의 오른쪽-위, 왼쪽-아래, 오른쪽-아래 꼭지점이 될 가능성이 있다. 구멍의 꼭지점이 될 가능성이 있는 칸들의 개수를 세고 더했을 때 0개가 되면 비로소 색칠된 칸들은 직사각형 영역을 이루는 것을 알 수 있다.


즉, 직사각형의 꼭지점이 될 가능성이 있는 칸이 4개, 구멍의 꼭지점이 될 가능성이 있는 칸이 0개라면 직사각형을 이룬다.


칸을 하나씩 색칠해나가는 매 단계마다 직사각형의 꼭지점이 될 가능성이 있는 칸이 4개, 구멍의 꼭지점이 될 가능성이 있는 칸이 0개인 단계 수를 구하면 쿼리에서 요구하는 아름다운 부분직사각형 영역의 개수가 되는 것이고, 이를 segment tree를 잘 사용하여 서로 다른 두 칸에 적힌 수를 서로 바꿀 때마다 $O(\lg HW)$ 시간에 원하는 답을 구할 수 있다. 이 과정은 자료구조를 기술적으로 잘 사용하는 영역이므로 설명을 생략하며 첨부된 코드를 참고하길 바란다.


이 문제를 해결하는 총 시간복잡도는 $O(HW + Q \lg HW)$이며, 실제 계산량은 시간복잡도 앞에 상수가 꽤 붙어 시간제한이 많이 빡빡해서 나름 최적화가 필요했다.



3. werewolf


정점이 N개, 간선이 M개인 무방향성 그래프가 주어진다. 정점에는 0이상 N-1이하의 번호가 서로 다르게 매겨져있다. Q개의 쿼리가 주어지고, 각 쿼리마다 s, e, l, r 값이 주어진다. 이는 정점 s부터 시작해서 정점 r까지 l, r 이라는 특성 값을 늑대 인간이 여행을 할 수 있는지를 물어보는 것이다. l, r이라는 특성 값을 가진 늑대 인간은 초기에 인간 상태로 여행을 시작하며 인간 상태일 떄는 정점 번호가 l 미만인 곳에 가지 못한다. 인간 상태로 여행을 하다가 정점 번호가 l이상 r이하인 곳에서 늑대로 변신할 수 있으며, 여행이 끝날 때에는 늑대 상태여야한다. 늑대 상태일 때는 정점 번호가 r 초과인 곳을 가지 못한다. 이러한 Q개의 쿼리를 해결하는 것이 문제이며, 쿼리를 오프라인(비실시간)으로 해결해도 된다.


다음와 같은 그래프가 주어졌다고 하자.


빈 그래프에서 0번 정점부터 5번 정점까지 차례대로 추가했을 때, connected component들이 서로 합쳐지면서 최종 그래프는 connected graph가 될 것이다. 여기서 connected component들이 합쳐지는 과정을 루트가 있는 트리로 그리면 다음과 같다.



위 트리에서 루트는 5번 정점이 된다. 트리에서 0번 정점에서 1번 정점으로 가는 경로에서 가장 번호가 큰 정점은 3번 정점이며, 이는 원래 그래프에서 0번 정점에서 1번 정점으로 가는 경로들 중 정점 번호 최대값의 최소값이다. 또한 이는 0번 정점과 1번 정점의 LCA(최소공통조상)이 된다.


마찬가지로 반대 순서로 빈 그래프에서 5번 정점부터 0번 정점까지 차례대로 추가했을 경우로 루트가 있는 트리를 그리면 아래와 같이 나온다.



이번에는 루트가 0번 정점이 되며. 마찬가지로 트리에서 2번 정점에서 4번 정점으로 가는 경로에서 가장 번호가 작은 정점은 1번 정점이며, 이는 원래 그래프에서 2번 정점에서 4번 정점으로 가는 경로들 중 정점 번호 최소값의 최대값이다. 또한 이는 2번 정점과 4번 정점의 LCA(최소공통조상)이 된다.


이렇게 두 종류의 트리를 구하고 트리에서 LCA가 가지는 의미를 알게되면, 문제에서 주어지는 쿼리를 다른 말로 바꿀 수 있다. 쿼리에서 s, e, l, r이 주어졌다고 하자. 루트가 0인 트리에서 정점 s의 조상 중 번호가 l 이상인 가장 높은 조상의 정점 번호를 x라 하고, 루트가 N-1인 트리에서 정점 e의 조상 중 번호가 r 이하인 가장 높은 조상의 정점 번호를 y라고 했을 때, 루트가 0인 트리에서 x의 서브트리에 있는 정점들과, 루트가 N-1인 트리에서 y의 서브트리에 있는 정점들 중 겹치는 것이 있는지를 물어보는 것으로 쿼리를 바꿔 생각할 수 있다.

예를 들어, 위 상황에서 s=4, e=2, l=1, r=2 라고 했을 때, x=1, y=2가 되며, 루트가 0인 트리에서 x의 서브트리에 있는 정점들은 1, 2, 3, 4, 5이고, 루트가 N-1인 트리에서 y의 서브트리에 있는 정점들은 1, 2가 된다. 겹치는 정점이 있으므로 쿼리에 대한 답은 가능하다가 된다.

또 다른 예로, 위 상황에서 s=4, e=2, l=2, r=2 라고 했을 때, x=3, y=2가 되며, 루트가 0인 트리에서 x의 서브트리에 있는 정점들은 3, 4가 되고, 루트가 N-1인 트리에서 y의 서브트리에 있는 정점들은 1, 2가 된다. 겹치는 정점이 없으므로 쿼리에 대한 답은 불가능하다가 된다.


서브트리 두 개에 겹치는 정점이 있는지 확인을 빠르게 해주기 위해서는 두 종류 트리에 있는 각 정점들을 DFS 순서로 번호를 다시 매겨야한다.


위 그림에서 파란색 수는 루트가 N-1인 트리에서 DFS 순서로 번호를 다시 매긴 것이고, 빨간색 수는 루트가 0인 트리에서 DFS 순서로 번호를 다시 매긴 것이다. 파란색 수를 인덱스로 생각하고 빨간색 수를 그 인덱스에 해당하는 값으로 생각하고 배열을 만들면 다음과 같이 나온다.



언급했던 예제 상황 중 x=1, y=2일 때 겹치는 정점이 있는 지 확인하는 것은 루트가 0인 트리에서 x의 서브트리에 있는 정점의 빨간색 수 범위는 2이상 6이하다. 루트가 N-1인 트리에서 y의 서브트리에 있는 정점의 파란색 수 범위는 5이상 6이하다. 즉, 새로 만든 배열의 부분 배열인 인덱스 5~6 사이에 2이상 6이하인 값이 있는지를 물어보는 것과 같다.

두 번째 예제 상황에서 x=3, y=2일 때 겹치는 정점이 있는 지 확인하는 것은 루트가 0인 트리에서 x의 서브트리에 있는 정점의 빨간색 수 범위는 5이상 6이하다. 루트가 N-1인 트리에서 y의 서브트리에 있는 정점의 파란색 수 범위는 5이상 6이하다. 즉, 새로 만든 배열의 부분 배열인 인덱스 5~6 사이에 5이상 6이하인 값이 있는지를 물어보는 것과 같다.


새로 구한 배열을 만들었을 때, 쿼리는 merge sort tree를 이용하여 쿼리당 $O(\lg^2 N)$ 시간복잡도로 온라인으로 해결할 수 있다. 이 때 총 시간복잡도는 $O(M \lg N + Q \lg^2 N)$이 된다.



이 문제에서는 오프라인으로 쿼리가 주어지므로 merge sort tree에서의 탐색을 오프라인으로 진행했을 경우 총 시간복잡도는 $O(M \lg N + Q \lg QN)$가 된다.



저작자표시

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

IOI 2018 Day 2 문제 및 해법  (0) 2018.09.07
공유하기 링크
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
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
글 보관함