3회 모의고사는 DP-like 문제 8개로 만들었습니다.
접기
솔직히 이거 분류가 왜 DP인지 모르겠습니다. 그래도 좋은 문제라서 넣었어요.
문제의 핵심은 i번 열차를 몇 번 타게 되는지 카운트해주는 것입니다.
Range-Update Fenwick / Segment Tree를 이용하면 간단히 \(O(n\lg n)\)에 해결할 수 있습니다.
다만 이 경우에는 쿼리(i번 열차를 몇 번 타는가?)에 대한 답을 online으로 구할 필요가 없고, 맨 마지막에 한 번만 구하면 된다는 특성을 이용하면 \(O(n)\) 복잡도에 해결할 수 있습니다.
배열 F[1..n]을 잡고,
구간 [s,e)에 1을 더해주는 업데이트가 있다면
F[s] += 1;
F[e] -= 1;
을 실행한 뒤
맨 마지막에 F[1] + ... + F[i]가 답이 됩니다.
접기 접기
E[i][j] := i층짜리 건물을 j개의 금고로 test할 때 필요한 최소 횟수.
E[i][1] = i.
E[i][2] = \(\sim \sqrt{2i}\). (정확히는 \(\frac{k(k+1)}{2} > i\)인 최소 정수 \(k\))
E[i][j] = \(\left\lfloor \lg i \right\rfloor +1\) \((j > \left \lfloor \lg i \right \rfloor )\)이 됨이 well known이다.
저 세 조건을 모두 만족하는 closed-form을 찾겠다는 건 약간 무모한 생각인 것 같다... 정직하게 DP를 잡자.
\(j > 1\)에 대해서, 아무 층(\(k\)층)에서 금고를 떨어뜨렸을 때 부서졌다면 \(E(k-1,j-1)\)번, 부서지지 않았다면 \(E(i-k,j)\)번의 추가적인 조사가 필요함을 알 수 있다. 이를 바탕으로 DP 식을 세우자.
$$ E(i,j) = 1 + \min_{1 \le k \le i} \left( \max \{ E(k-1,s-1) , E(i-k,j) \} \right) $$
**Thanks to easrui**
하지만 한 가지 커팅을 해주면 복잡도 수준 의 발전이 있는데, 만약 \(E(i,j-1) \le j\)라면 금고를 하나 더 추가하는 의미가 없으므로 단순히 E[i][j] = E[i][j-1]을 대입한 뒤 커팅을 하면 된다. 이미 \(j > \lg i\)에 대해서 이 사실이 성립함이 well known이므로 못해도 \(O(n^2 \lg n)\)안에 돌아간다.
접기 접기
모든 인덱스는 시계방향으로, mod n으로 생각합니다.
\(D[i,j]\) : i번 케이크부터 시계 방향으로 j번 케이크까지를 먹으면서 얻는 최대 이익
base case : \(D(i,i) = 0\)
답 : \(D(i,i-2)\) (n이 홀수), \(D(i,i-1)\) (n이 짝수)
점화식 :
본인의 선택에 따라 여동생의 선택은 자동결정되므로, 이를 정직하게 시뮬레이션한다는 생각으로 DP를 채워줍시다. 점화식에서 알 수 있지만, DP는 구간의 길이 (j - i)가 증가하는 순서대로 채워주어야 합니다. 갖가지 예외처리를 현명하게 하면 AC가 뜹니다 ㅎㅎ
(* \(a \leftarrow b\) := \(a < b\)일 때 \(a = b\) 대입)
$$ \begin{cases} D[i-2,j] \leftarrow D[i,j]+A[i-2] & D[i-1,j+1] \leftarrow D[i,j] + A[j+1] & (A[i-1] > A[j+1]) \\ D[i,j+2] \leftarrow D[i,j]+A[j+2] & D[i-1,j+1] \leftarrow D[i,j] + A[j+1] & (A[i-1] < A[j+1]) \end{cases}$$
접기 접기
DP는 아니지만 아주 괜찮은 문제죠!
Naive는 \(O(n^3)\)으로 TLE.
정렬 이후 upper_bound와 lower_bound를 열심히 쓰면 \(O(n^2 \lg n)\)으로 AC는 받을 수 있지만 정해의 구현이 훨씬 간단합니다.
용액을 특성값 순서대로 정렬합니다. \(t\)번째 용액의 특성값을 \(A[t]\)라고 합시다.
가장 좋은 해 \(i < j < k\)를 찾으면서 \(i\)를 fix합시다. 이제 해당 조건에서 특성값을 0에 가깝게 하는 나머지 두 인덱스 \(j < k\)를 찾아주면 됩니다. 이 과정에서 brute-force를 사용하면 복잡도가 \(O(n^3)\)이 되겠죠.
맨 처음에 j = i+1, k = n-1 (0-based)으로 설정합니다.
이 때 \(A[i] + A[j] + A[k]\)가 기존의 값보다 좋다면(0에 가깝다면) 갱신해줍니다.
그리고 이 step이 탐색 시간을 줄이는 key point입니다.
\(A[i] + A[j] + A[k] > 0\)이라면 k--;
\(A[i] + A[j] + A[k] < 0\)이라면 j++;
생각해내기 어렵지만 납득하기는 쉬운 사실입니다.
A[i] + A[j] + A[k] > 0이라면 같은 j에 대해서 더 큰 k는 볼 필요가 없습니다. 다음 경우도 마찬가지입니다.
따라서 한 번에 무조건 1씩 [j,k]의 길이를 줄일 수 있고, 이를 i = 0..n-3까지 반복하면 \(O(n^2)\) solution이 됩니다.
접기 Convex Hull Trick을 이용하는 하고 많은 변태적인(...)문제 중에는 가장 간단한 문제입니다.
MWT.pdf