CS and mathematics

문제 해석

\(N\)개의 자연수가 주어질 때, 이것들을 원형으로 배치하여 이웃하는 두 수의 차이의 최댓값을 최소로 만들려고 한다. 다시 말해, 주어진 자연수들의 순열 \(x_1, x_2, \cdots, x_N\)에 대하여

\[D = \max_{i=1}^N |x_i - x_{i+1}| \quad (x_{N+1} := x_1)\]

를 최소화하고자 한다. 그런 순열 중에서 사전순으로 가장 앞서는 것을 구하라.

접근

사전순 최소 조건을 신경쓰지 않고 \(D\)의 최솟값만 먼저 DP로 구한 다음, 사전순 최소해는 greedy하게 구성할 것이다.

일반성을 잃지 않고 수들의 인덱스를 크기 순으로 매기자: \(x_1 \le \cdots \le x_N.\)

첫 번째로 관찰할 것은 \(x_1\)부터 한 바퀴 돌 때 \(x_N\)까지 단조롭게 올라갔다가 내려오는(bitonic) 순열 중에 최적해(\(D\)를 최소화하는 해)가 존재한다는 사실이다. 식으로 표현하면,

\[[x_1, a_1, a_2, \cdots, a_{M-1}, a_{M}, x_N, b_{L}, b_{L-1}, \cdots, b_2, b_1] \quad\cdots(1)\]

과 같이 배치했을 때 \(a_1 \le a_2 \le \cdots \le a_{M}\)과 \(b_1 \le b_2 \le \cdots \le b_{L}\)를 만족하는 경우들 중에 최적해가 존재한다. 이것을 만족하지 않을 경우, 만족하도록 재배열하면 \(D\)가 그대로거나 감소하기 때문이다.

\(x_1\)부터 \(x_j\)까지를 사용하여 하나는 \(x_1\)부터 \(x_i\)까지, 다른 하나는 \(x_1\)부터 \(x_j\)까지 올라가고 서로 disjoint한 2개의 단조증가 수열을 만들 때, 최대 인접 차의 최솟값을 \(dp(i,j)\)라고 정의하자. 두 수열을 구별할 필요가 없으므로(뒤집으면 동일하니까), 일반성을 잃지 않고 \(i<j\)이라 한다. 엄밀하게는 아래와 같다.

\[dp(i,j) = \min \left[ \max \left[ a_1-x_1, a_2-a_1, \cdots, a_{M}-a_{M-1}, b_1-x_1, b_2-b_1, \cdots, b_{L}-b_{L-1} \right] \right]\]
  • \[1 < i < j \le N\]
  • \[x_1 \le a_1 \le \cdots \le a_{M} = x_i\]
  • \[x_1 \le b_1 \le \cdots \le b_{L} = x_j\]
  • \(\{a_1, \cdots, a_M, b_1, \cdots, b_L\}\)은 \(\{x_2, \cdots, x_j\}\)에 하나씩 대응한다.

상태 전이 방법은 \(x_{j-1}\)가 어느 쪽에 붙느냐를 고려한다. \(i\)와 \(j\)의 차이가 \(1\)보다 크면 \(x_{j-1}\)은 \(x_j\)의 직전에 올 수밖에 없고, 그렇지 않으면 \(x_i\)와 \(x_{i+1}(=x_j)\)가 각각 두 수열의 끝이므로 \(x_{i+1}\)의 직전에 누가 올지 선택하면 된다. 엄밀하게는 아래와 같다.

\[\begin{align} dp(2,3) &= x_3 - x_1 \\ dp(i,j) &= \begin{cases} \min_{2 \le k < i} \max \left[ dp(k,i), x_{i+1} - x_k \right] & \text{if } j = i+1 \\ \max \left[ dp(i,j-1), x_j - x_{j-1} \right] & \text{if } j > i+1 \end{cases} \end{align}\]

계산해야 하는 state는 \(1 < i < j \le N\)로 모두 \(\mathcal{O}(N^2)\)개다. 이 중 \(j = i+1\)인 것은 \(\mathcal{O}(N)\)개 있고 개당 \(\mathcal{O}(N)\) 시간이 걸리며 나머지는 \(\mathcal{O}(1)\) 시간이 걸리므로 총 \(\mathcal{O}(N^2)\) 시간에 모두 계산할 수 있다.

마지막으로, 두 수열 중 \(x_N\)으로 끝나는 쪽의 반대쪽이 무엇으로 끝날지 \(\mathcal{O}(N)\)가지 경우를 순회하여 \(D\)의 최솟값 \(D^*\)를 구할 수 있다.

\[D^* := \min D = \min_{2 \le s < N} \max \left[ dp(s,N), x_N - x_s \right]\]

\(D^*\)를 알면 사전순으로 가장 앞서는 최적해를 greedy하게 찾을 수 있다. 식 \((1)\)과 같은 bitonic 수열이 될 것인데, \(x_2\)부터 \(x_N\)까지 차례로 보면서 최대한 \(a\) 진영에 붙이고, \(b\) 진영에서 인접 차가 \(D^*\)를 초과하려 할 때만 \(b\) 진영에 붙이면 된다.

여담으로 \(D^* = \max_{i=1}^{N-2} \left[ x_{i+2} - x_i \right]\)라는 claim이 있다.[1] 이렇게 구현해도 AC가 나오고 반례도 찾지 못했지만 증명을 아직 이해하지 못했다.

코드

1129.cpp

참고문헌

[1] Sit N people around a table so as to minimize the maximum difference between any two adjacent people

참고