JOI 2018

https://www.ioi-jp.org/joi/2017/2018-ho/index.html

https://oj.uz/problems/source/307

1, 2번까지는 무난하게 풀 수 있었고, 3, 4번을 푸는데 내 힘으로 풀지 못하고 여러 블로그들과 공식 풀이를 보며 풀어 이틀이 걸렸다. 5번 문제는 공식 풀이 슬라이드를 봐도 도무지 이해가 안가 나중에 다시 풀어봐야 할 것 같다. 이번 셋을 풀면서 느낀 점은 DP의 중요성과, 그래프 문제들은 역시 관찰과 연습만이 답인 것 같다. 또한, 역시 JOI 문제들은 문제의 질과 수준 모두 매우 좋은 것 같다.

1. stove

만약 K번 킬 수 있다면 각 난로를 켜야하는 시간에만 켜놓으면 된다. 그럼, 그 이하라면 어떻게 해야 할까?

전체 구간을 기준으로 난로를 켜야 하는 시간들 사이의 간격을 생각해 보자. 난로를 킬 수 있는 기회가 줄어들면 그 구간들 사이의 간격중 하나를 골라서 계속 켜놓아야 한다. 이를 그리디로, 가장 시간이 짧은 간격부터 골라서 켜 놓으면 된다.

시간 복잡도 : O(NlgN)

2. art

가장 먼저, 답이 a의 최대 최소에 의해 결정되므로, 전체 값들을 a에 대하여 정렬해놓고 시작하자.

이제, amin 값을 하나 고정시키고 시작하자. amin 보다 오른쪽에 위치한 값들에 대하여 (amin 부터 amax 까지의 b 값들의 합) - (amax - amin) 값들의 최댓값을 계산하면 된다.

이를 다시 말하면 답은 amin 을 하나 고정시킨 후, 모든 오른쪽 값들 중, (pbsum[amax] - pbsum[amin]) - amax + amin 을 계산하면 된다. 여기서 amin을 고정시켰으니 pbsum[amin], amin 값은 고정되었음을 잘 살펴보자.

남은 값들은 pbsum[amax]-amax 이니 이 값들 중 최댓값을 찾으면 된다.

이러한 문제는 구간에서 최댓값을 찾는 문제로 바뀔 수 있으며, segment tree 를 사용하여 풀 수도 있지만, 가장 쉬운 방법으로는 미리 전처리한 후, 뒤에서부터 거꾸로 스택에 오름차순으로 쌓아 놓으면 된다. 스택에 쌓아 놓은 값들을 기준으로 앞에서 쭉 훑으며 값들을 하나하나 스택에서 빼주며 계산하면 된다.

시간 복잡도 : O(NlgN)

3. dango

이 문제 느낌의 타일 채우기 문제는 많은 문제들이 2-SAT 혹은 매칭으로 바뀌어 풀린다. 하지만 이 문제는 다르다.

Subtask 2

첫번째로 문제를 보고 떠올릴 수 있는 생각은 N*M 격자를 2*1 크기의 타일로 채우는 문제이다. 이러한 문제들은 한쪽 축을 기준으로 나머지 축에 대하여 비트마스킹 DP 를 통해 풀어나갈 수 있다. 2*1 타일 채우기는 그 점을 기준으로 전 한줄의 정보만 필요해 O(NM*2^M) 을 통해 풀 수 있었다. 이제는 한 타일의 크기가 3칸이기 때문에 전 2줄에 대해서 위에서부터 보았을 때 연속한 몇개의 칸이 사용 불가능한가를 dp의 값으로 갖고 있다면 O(NM*3^M) 으로 부분점수를 긁을 수 있다.

시간 복잡도 : O(NM*3^M)

Subtask 3

N, M <= 3000 이니, 위의 지수 시간 복잡도를 갖는 알고리즘보다 개선된 알고리즘이 필요하다. 

위의 O(NM*3^N) 풀이를 다시 생각해 보자. 현재 타일부터 오른쪽으로 RGW 를 만족한다면, 오른쪽으로 타일을 배치할 수 없는 경우는 오른쪽, 오른 오른쪽 칸이 이미 차있어야 한다. 이를 다시 생각해보면 대각선 위 칸이 R, 그 대각선 위 칸이 R이어야 이미 차있을 수 있다는 것을 알 수 있다. 이를 통해 뭔가 오른쪽 위의 대각선으로 생각해봐야 한다는 것을 알 수 있다.

위의 관찰을 통해 이를 알 수 있다. 완성된 답에서의 초록색 타일만을 생각해보자. x+y=t의 직선 위에 어떤 초록색 타일이 있어 이 타일을 지나는 3*1 블럭은 다른 대각선 상의 초록색을 중심으로 하는 블럭들과는 절대 영향을 미칠 수 없음을 알 수 있다. 따라서 각 대각선에 대하여 모두 독립적인 일차원 문제가 되었다.

이제 마지막으로 분리한 일차원 문제를 풀어보자. 이번에도 DP 로 해결할 수 있다. 

다음과 같이 상태를 나누자. 어떤 G에 대하여 오른쪽 위 칸, 왼쪽 위 칸이 이미 사용되어있는가를 각각 0, 1, 2의 상태로 저장하고, 이를 통해 dp[x][state] 로 DP 를 돌리면 된다.

시간 복잡도 : O(NM)

4. commuter

문제를 딱 봐서는 별 아이디어가 떠오르지 않는다. 최단경로가 여러 개가 될수 있다는 것 자체가 매우 골치아픈 일이기 때문에 몇가지의 관찰을 하지 않으면 어려울 수 있다. 앞으로 확실히 그래프 문제를 계속풀어봐야 겠다고 느낄수 있게 해준 문제이다.

가장 중요한 관찰은 다음과 같다. -> S에서 T로 가는 경로를 하나 골랐다고 생각하자. 이 경로의 가중치들을 모두 0으로 만들었다면, U에서 V로 가는 최단경로는 S에서 T로 가는 경로에 아에 들어가지 않던가, 한번 진입했다가, 한번 나간다. 만약 두번 이상 나갔다 들어왔다를 반복한다면 가장 먼저 들어온 시점과 가장 마지막으로 나간 시점을 생각했을 때, 그 둘을 이어 주면 무조건 더 짧은 최단거리가 나오기 때문이다. 따라서 만약 S에서 T까지의 경로를 하나 정했다면, 정답은 그 경로상의 모든 점에 대해서 U까지의 최단거리 중 최소값 + 모든 점에 대해서 V까지의 최단거리 중 최솟값 이 될 것이다. 

이제 그 경로를 하나 정하면 된다. 일단 S에서 T로 가는 최단경로가 아닌 간선들을 지우자. 그리고 실제 이동한 경로들에 방향성을 부여하면 하나의 DAG 가 나온다. 이 과정은 (u, v) 가 살아 남으려면 dist[u]+(u, v)=dist[v] 가 되면 된다. 이 완성된 DAG 에서 무엇을 해야 할까?

그래프를 DAG로 만드는 많은 이유들 중 하나는 위상정렬을 한 후 DP를 돌리기 위함이다. 이 문제에서 어떻게 DP를 돌릴 수 있을까? 끝점에서 생각해 보자. DAG 에서 T로 오는 모든 간선들에 대해, U까지의 최단거리 중 최솟값 dp1, V까지의 최단거리 중 최솟값 dp2 를 알고 있다고 생각하자. 정점 v1, v2, v3, v4, ... 에 대해 그 정점을 최단거리로 선택했을 때의 답은 min(dp1[v1], DU[T])+min(dp2[v2], DV[T]) 가 된다. 이제 이 점화식으로 DAG 에서 dp를 잘 돌려주면 된다.

사실 아직 이 DAG 에서의 DP 가 왜 성립하는지는 잘 모르겠다. DP를 사용하기 위해서는 각 단계에서 최적의 선택을 해도 됨을 보여주는 Optimal Substructre (OS) 가 필요한데, 여기서는 고려해야할 값이 두개이고, 이 두개의 합을 최소화하는 상황에서 각 단계에서 최적의 선택을 해도 되는지를 잘 모르겠다. 나중에 더 생각해 보아야 할 것 같다.

(수정)

다시 한번 풀어봤을 때 이번에는 더 정확한(?) 풀이를 발견했다. 아까와 같이 전체 S->T의 경로의 최단경로를 생각하면, 이 중 U까지의 최단경로가 나오는 점과 V까지의 최단경로가 나오는 점을 기준으로 전체 경로를 두개로 쪼갤 수 있다. 이와 같이 생각하면 S에서 한번, T에서 한번 dp를 통해 U, V까지의 최단경로를 모두 계산해줄 수 있다.

시간 복잡도 : O(ElgV)

5. snake

아직 해결하지 못하였다.