IOI 2008 Day 2 Solutions

1. Teleporters

각각의 텔레포터를 정점이라 두고, 적당히 간선을 연결하여 그래프를 형성할 것이다. 편의를 위해 각각의 텔레포터를 텔레포터로 들어가는 정점과, 텔레포터에서 나오는 정점의 2개로 분리하도록 하자. 즉 한 쌍의 텔레포터는 4개의 정점으로 표현된다. 또한 시작점과 끝점에도 정점을 각각 하나씩 만들어 주자. 이제 유향 간선으로 정점들을 이어줄 것인데, 각 정점을 2개로 분할하였기 때문에 각 정점의 indegree와 outdegree는 둘다 1이다. 시작점과 끝점은 각각 outdegree와 indegree가 1이다. 이러한 방법으로 이어준 그래프의 컴포넌트들의 모양을 관찰해보자.

 

(1) 각각의 컴포넌트는 단순 사이클이거나 직선이다.

pf) 시작점에서 끝점으로 항상 갈 수 있다는 문제의 조건에 의하여, 시작점과 끝점을 포함하는 그래프는 직선일 수밖에 없다. 이 컴포넌트를 제외한 남은 컴포넌트들은 각각의 정점의 in/outdegree가 1이며, 정점의 개수와 간선의 개수가 같으므로 단순 사이클이다.

 

직선 컴포넌트에서 시작점부터 끝점까지 가는 경로에 사용하는 텔레포터의 수는 (간선의 수-1)/2이다.

또한 사이클 컴포넌트 상에서 한바퀴를 돌았을 때 사용하는 텔레포터의 수는 (간선의 수)/2이다.

따라서 각 컴포넌트에 대해 텔레포터를 이용하는 횟수에 대한 배열 T[0], T[1], T[2], .... 을 만들어 위의 값을 담아두도록 하자. 이때 0번째 컴포넌트는 직선 컴포넌트이다.

 

이제, 텔레포터를 설치했을 때 그래프에서 무슨 일이 일어나는지 관찰해보면, 텔레포터를 설치하는 행동은 두개의 컴포넌트를 합치거나, 새로운 컴포넌트 하나를 만드는 행동이 된다. 구체적으로 아래에 제시된 3가지 경우 중 하나의 상황이 발생한다.

 

a) 사이클 i와 사이클 j를 합친다. (0<i<j)

이 연산을 T에 대해 적용해보면, T[i]=T[i]+T[j]+2이다.

b) 직선 0과 사이클 i를 합친다. (0<i)

이때 T[0]=T[0]+T[i]+2이다.

c) 하나의 컴포넌트 i 내부에 정점이 추가되고 새로운 컴포넌트가 생긴다. (0<=i)

이때 T[i]=T[i]+1이고, T[x]=1인 컴포넌트 x가 새롭게 생긴다.

 

위의 관찰을 토대로 우리는 주어진 문제를 다음의 간단한 문제로 치환할 수 있게 된다 : 정해져 있는 T[0], T[1], ....에 k번의 a/b/c 연산을 실행하여 T[0]을 최대화하여라.

 

이 문제는 몇가지의 추가적인 관찰을 통해 해결할 수 있다.

 

(2) a번 연산은 없다고 생각해도 좋다.

pf) 우리의 목표는 T[0]의 값을 최대화하는 것이다. 따라서 a번 연산을 x번(x>=1) 사용한 뒤 b번 연산을 통해 합쳐주어야 a번 연산을 한 의미가 있다. 이때 T[0]의 값은 (a번 연산을 적용한 사이클 x+1개의 T값의 합)+2*x+2인데, 이때 연산을 적용해준 x+1개의 컴포넌트에 대해 각각 b번 연산을 적용해도 T[0]의 값은 같다. 고로, 모든 유의미한 a번 연산은 b번 연산으로 치환될 수 있다.

 

(3) b번 연산은 c번 연산보다 효율이 좋다.

pf) 사실 자명하다. b번 연산을 통해 직선의 길이는 최소 3 이상 증가하지만, c번 연산은 길이가 1 늘어나는 것에 그친다.

 

위의 관찰은 다음의 그리디 알고리즘을 도출해낸다: T값이 큰 컴포넌트부터 b번 연산을 진행해 준 뒤, 더이상 사이클 컴포넌트가 남지 않았으면 c번 연산과 b번 연산을 번갈아 가면서 진행해준다. c번 연산을 할 때마다 T[0]은 1 증가하고, 그 다음의 b번 연산에서는 T[0]이 3 증가하므로 남은 부분은 전체 상수시간에 간단히 해결 할 수 있다. 시간복잡도는 T값의 정렬때문에 O(NlogN)이다.

 

2. Garden

S[i]를 1~i번까지 봤을 때 (L의 개수-P의 개수)라 하자. 문제의 조건은 임의의 구간 [s, e]를 잡아 그 사이 S값들의 max값-min값이 2보다 작다는 것과 동치이다. 문제에서는 저러한 조건을 만족하는 문자열 하나가 주어져 그 문자열이 전체 가능한 배열 중 사전순으로 몇번 오는 것인지 출력하라고 요구하는데, 이는 P가 나오는 지점마다 적당한 연산을 취해준 값을 더해준 것으로 알 수 있다.

 

예를 들어, "PLPPL"이라는 문제의 조건을 만족하는 문자열이 사전순으로 몇번째인지 판별하는 것은, ("L****" 꼴의 배열 개수)+{"PLL**"꼴의 배열 개수}+{"PLPL*"꼴의 배열 개수}+1을 계산하는 것으로 충분하다. 이것은 간단한 조합 문제로, 하나의 쿼리당 거듭제곱 연산 상수개가 필요하여 총 O(NlogN)에 해결할 수 있다. S[i+1]와 S[i]의 차이는 항상 1이라는 사실을 잘 이용하면 된다.

 

3. Pyramid Base

이 문제는 특이하게 만점을 받으려면 두개의 서로 다른 알고리즘을 작성해야 한다. 두개의 알고리즘을 차례차례 설계해보자.

 

3-1) Pyramid Base 2 (BOJ 기준)

문제에서 주어지는 B값이 0이 아닌 버전이다. 2번 문제는 파라메트릭 서치로 접근해보도록 하겠다. 따라서 한변의 길이가 r인 정사각형이 들어갈 수 있는지 판별하는 결정 문제로 본 문제를 환원했다. 정사각형은 왼쪽 아래 점이 정해지면 유일하게 모양이 하나로 결정된다. 이 점을 편의상 (x,, y)라 하겠다. 이 상황에서 정사각형과 문제에서 주어진 직사각형이 겹치는 조건에 대한 하나의 명제가 성립한다. 직사각형은 (왼쪽 아래 점의 좌표)~(오른쪽 위 점의 좌표)로 표기하도록 하겠다.

 

(x, y)에 있는 한 변의 길이가 r인 정사각형이 (sx, sy)~(ex, ey)와 겹치는 것과 좌표 (x, y)가 (sx-r+1, sy-r+1)~(ex, ey) 내부에 있는 것은 필요충분조건이다.

 

따라서 각 직사각형 (sx, sy)~(ex, ey)를  (sx-r+1, sy-r+1)~(ex, ey)로 바꾸고 이를 시작점의 x좌표 기준으로 정렬한 뒤 y축 을 나타내는 세그먼트 트리를 왼쪽에서 오른쪽으로 스위핑해주도록 하자. 이때 좌표의 범위가 매우 크기 떄문에 좌표압축을 해주도록 한다. 왼쪽 변을 추가할 때에는 해당 y축 구간에 직사각형의 가중치를 더해주고, 오른쪽 변에서는 같은 가중체를 뺴주는 식으로 구간 업데이트가 있는 min 세그먼트 트리를 관리해주면, 전체 격자에서 가중치를 최소로 하는 정사각형의 배열을 알 수 있게 되고, 이때의 가중치가 B 이하이면 true, 초과이면 false를 return해주면 된다. 이때 시간복잡도는 O(PlogPlogN)정도로 혹자는 이 알고리즘으로 B=0이지만 P가 400000으로 큰 Pyramid Base 3을 풀 수 있지 않을까라고 생각할 수 있다. 그러나 P<=1000인 Pyramid Base 2에서도 (본인 코드 기준)876ms 씩이나 걸리기 때문에 이 알고리즘이 3번 문제에서도 먹힐 일은 없다고 봐도 무방하다.

 

 

3-1) Pyramid Base 1&3 (BOJ 기준)

문제에서 항상 B=0을 만족한다. Pyramid Base 2처럼 파라메트릭으로 접근하면 시간복잡도 개선의 여지가 거의 보이지 않기 떄문에 다른 접근을 해보자. 정사각형의 오른쪽 x좌표를 고정시킨 다음, 그 상황에서 정사각형의 최대 크기를 찾아보자. 이를 하기 위해 투포인터를 사용한다. 왼쪽 포인터를 l, 오른쪽 포인터를 r이라 할 때, 정사각형의 왼쪽의 x좌표가 l이고 오른쪽의 x좌표가 r인 정사각형이 존재하기 위해서는  그 사이에 있는 직사각형만을 고려했을 때 직사각형이 존재하지 않는 연속된 y좌표의 길이가 r-l+1 이상이면 된다. 이는 구간 업데이트가 있는 DNC 세그먼트 트리로 간단하게 구현할 수 있다. 시간복잡도는 O(PlogP)이다.