JOI 2013
1. 전구 장식
https://www.acmicpc.net/problem/5527
간단한 문제이다.
홀수 번째 전구들의 상태를 모두 바꿔보자.
그러면
(on ... on)(off ... off)(on ... on)
(off ... off)(on ... on)(off ... off)
위와 같은 전구열의 최대 길이를 찾는 문제가 되고, 쉽게 구할 수 있다.
시간복잡도는 $O(N)$.
2. 달려라 IOI 열차
https://www.acmicpc.net/problem/5528
마지막에 차고지에 열차가 남아도 되는걸 몰라서 헤맸다...
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이다.
시간복잡도는 $O(NM)$.
3. 저택
https://www.acmicpc.net/problem/5529
이상한 스위치가 있지만 결국은 최단경로 문제다. 시작점과 끝점 처리가 조금 귀찮았다.
집을 복사해서 2개로 만들자.
1번 집은 상하로만 움직일 수 있고, 2번 집은 좌우로만 움직일 수 있다.
1번 집에서, 각 스위치에 대해 위로 가장 가까운 스위치, 아래로 가장 가까운 스위치를 길이가 거리와 같도록 간선으로 이어준다.
2번 집에서도 좌우로 똑같이 해준다.
그리고 각 스위치가 있는 방들에 대해 1번 집과 2번 집을 길이 1인 간선으로 이어준다.
이 그래프는 정점이 $O(K)$개, 간선이 $O(K)$개 있는 그래프가 된다.
다익스트라 알고리즘을 통해 최단 시간을 구할 수 있다.
시간복잡도는 $O(KlogK)$.
4. JOIOI 탑
https://www.acmicpc.net/problem/5530
상당히 헷갈린다. 글로 증명을 쓰려다보니 너무 대충 적은 것 같다.
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를 이용해서 구현할 수 있다.
시간복잡도는 $O(Na(N))$.
5. 버블 정렬
https://www.acmicpc.net/problem/5531
버블 정렬의 교환 횟수는 유명한 문제다. 문제를 적절히 변형하면 풀이를 찾을 수 있다.
같은 수가 있을 수도 있어서 처리가 조금 길어질 수 있다.
$(i, a_i)$에 점을 찍었을 때, $(x, a_x)$, $(y, a_y)$ $(x<y, a_x>a_y)$를 꼭짓점으로 하는 직사각형이 포함할 수 있는 점 개수의 최대값을 찾아야 한다.
$(x, a_x)$ 왼쪽 위나 $(y, a_y)$보다 오른쪽 아래에 있는 점이 있다면 그것을 고르는 것이 이득이다.
따라서 $x$, $y$의 후보를 줄일 수 있다.
후보들을 $x_i$, $y_i$라고 하자. $(x_i<x_{i+1}, y_i<y_{i+1})$
$x_i<x_j$이면 $a_{x_i}<a_{x_j}$이고, $y$도 마찬가지로 성립한다.
각각의 $(i, a_i)$들은 $x_t$부터 $x_s$까지 연속적으로 관여한다. 마찬가지로 $y_p$부터 $y_q$까지 연속적으로 관여한다.
따라서 $y_1$부터 차례대로 관여되는 점들을 보면, 각각의 점들은 한 번 들어가고 한 번 빠진다.
점을 넣을 때 $x_t$부터 $x_s$까지 세그먼트 트리를 이용해서 값을 더해주고, 점을 뺄 때 값을 빼 줄 수 있다.
각각의 $y$에 대해 세그먼트 트리에서 최대값을 구하면 답이 된다.
단, 점이 직사각형에 걸치거나 점들 중 직사각형을 만들 수 있는 쌍이 없을 때는 예외 처리를 해주어야 한다.
시간복잡도는 $O(NlogN)$.