[5/23] JOI 2013

홀수 번째 전구들의 상태를 모두 바꿔보자.

그러면

(on … on)(off … off)(on … on)

(off … off)(on … on)(off … off)

위와 같은 전구열의 최대 길이를 찾는 문제가 되고, 쉽게 구할 수 있다.

시간복잡도는 .

dp[0][i][j] = S에서 1~i-1, T에서 1~j-1를 외부 차고로 보냈을 때, OIOI…OI의 최대 길이

dp[1][i][j] = S에서 1~i-1, T에서 1~j-1를 외부 차고로 보냈을 때, IOIO…OI의 최대 길이

위와 같은 dp를 정의하자.

dp[0][i][j] = max(S[i] == ‘O’ ? dp[1][i+1][j]+1 : 0, T[j] == ‘O’ ? dp[1][i][j+1]+1 : 0)

dp[1][i][j] = max(S[i] == ‘I’ ? dp[0][i+1][j]+1 : -inf, T[j] ==’I’ ? dp[0][i][j+1]+1 : -inf)

dp 배열은 위와 같이 계산할 수 있다.

답은 dp[1][i][j] 중 최대값이다. dp[1][i][j]가 모두 -inf인 경우는 I 차량이 전혀 없을 때인데, 이 때의 답은 0이다.

시간복잡도는 .

집을 복사해서 2개로 만들자.

1번 집은 상하로만 움직일 수 있고, 2번 집은 좌우로만 움직일 수 있다.

1번 집에서, 각 스위치에 대해 위로 가장 가까운 스위치, 아래로 가장 가까운 스위치를 길이가 거리와 같도록 간선으로 이어준다.

2번 집에서도 좌우로 똑같이 해준다.

그리고 각 스위치가 있는 방들에 대해 1번 집과 2번 집을 길이 1인 간선으로 이어준다.

이 그래프는 정점이 개, 간선이 개 있는 그래프가 된다.

다익스트라 알고리즘을 통해 최단 시간을 구할 수 있다.

시간복잡도는 .

1. JOI, IOI의 OI는 최대한 뒤에 있는 것을 사용하는 것이 이득이다.

뒤에 있는 OI 대신 앞에 있는 OI가 사용되었다는 것은 두 가지 경우가 있다.

a) 뒤에 있는 OI의 I가 사용되지 않았거나 앞에 있는 OI의 I로 사용되었을 때 – 앞에 있는 OI를 뒤에 있는 OI로 바꿀 수 있다.

b) 뒤에 있는 OI의 I가 IOI에서 앞의 I로 사용되었을 때 – 

*(1)…O(2)…I(3)…O(4)…I(5)…O(6)…I(7) 꼴으로, 1-2-3과 5-6-7이 매칭되어 있다. (3이 4 뒤에 있을 때는 간단하다.)

3-6-7과 1-4-5로 바꿀 수 있다.

따라서 뒤에서부터 OI가 나타날 때마다 매칭하는 그리디를 생각할 수 있다.

2. IOI에서 앞의 I로 사용되던 I가 OI에서 뒤의 I로 교체되어야 할 때, 새로운 앞 글자는 기존의 I 왼쪽에 있는 가장 가까운, 사용되지 않은 J나 I를 선택하면 된다.

이것은 Union Find를 이용해서 구현할 수 있다.

시간복잡도는 .

에 점을 찍었을 때, , 를 꼭짓점으로 하는 직사각형이 포함할 수 있는 점 개수의 최대값을 찾아야 한다.

왼쪽 위나 보다 오른쪽 아래에 있는 점이 있다면 그것을 고르는 것이 이득이다.

따라서 , 의 후보를 줄일 수 있다.

후보들을 , 라고 하자.

이면 이고, 도 마찬가지로 성립한다.

각각의 들은 부터 까지 연속적으로 관여한다. 마찬가지로 부터 까지 연속적으로 관여한다.

따라서 부터 차례대로 관여되는 점들을 보면, 각각의 점들은 한 번 들어가고 한 번 빠진다.

점을 넣을 때 부터 까지 세그먼트 트리를 이용해서 값을 더해주고, 점을 뺄 때 값을 빼 줄 수 있다.

각각의 에 대해 세그먼트 트리에서 최대값을 구하면 답이 된다.

단, 점이 직사각형에 걸치거나 점들 중 직사각형을 만들 수 있는 쌍이 없을 때는 예외 처리를 해주어야 한다.

시간복잡도는 .