ABC339 E - Smooth Subsequence

Competitive Programming C++

2024-02-04

공식 에디토리얼

문제 링크
https://atcoder.jp/contests/abc339/tasks/abc339_e

원문 링크
https://atcoder.jp/contests/abc339/editorial/9210

\(dp_{i, j}\)를 인접한 \(2\)개 항의 차의 절댓값이 \(D\)이하에 해당하면서 끝이 \(j\)인 \((A_1, A_2, …, A_N)\)의 부분 수열의 길이의 최댓값이라고 합시다.

이 때,

\[dp_{i, j} = \Bigg\{\begin{align} \tag{\(j = A_i\)} &\max_{k \in [ A_i - D, A_i + D]} dp_{i - 1, k} + 1\\ \tag{\(j \neq A_i\)} &dp_{i - 1, j} \end{align}\]

이 성립합니다. 이 식을 따라 \(dp\) 배열을 계산해보면 정답을 얻을 순 있지만 시간복잡도와 공간복잡도가 \(\Theta(N^2)\)가 되어버립니다.

여기서 \(dp_{i - 1, j}\)와 \(dp_{i, j}\)의 값이 거의 모든 \(j\)에서 일치한다는 점을 이용해 빠르게 처리할 수 있습니다.

\(dp_{i, j}\)를 각각의 \((i, j)\) 쌍에 대해 배열을 돌려 쓰는 것으로, 위의 \(dp\)는 \(1\)차원 배열 \(dp\)를 가지고 \(i = 1, 2, …, N\)의 순서대로 \(dp_j\)를 \(\max_{k \in [ A_i - D, A_i + D]} dp_k + 1\)로 바꿔가면서 처리하면서 덮어쓸 수 있습니다.

이것으로 공간복잡도는 \(O(N)\)이 되었습니다. 시간복잡도는 \(\max\)를 브루트포스로 계산하면 \(\Theta(N^2)\) 그대로지만, 구간 \(\max\)와 점 업데이트 쿼리를 가진 세그먼트 트리를 이용해 \(O(N \log N)\)이 됩니다.

이번엔 불참

이번주 ABC는 다른 사정이 있어 불참이었다.
E 난이도를 보니 참가했더라도 E 못풀고 막혔을듯…

웰노운을 잘 먹어야 하는데 이런건 대체 어떻게 시간 내에 발상을 해대는건지 모르겠군.