문제 링크
- http://icpc.me/8874
문제 출처
- 2013 IOI Day1 3번
사용 알고리즘
- 세그먼트 트리
- DP
시간복잡도
- 쿼리당 $O(C^2 log R)$
풀이
$R$에 비해 $C$가 많이 작습니다.
$i, j$를 고정했을 때, $i$행의 어느 점에서 $j$행의 어느 지점으로 가는 $C^2$가지에 대해 미리 계산을 한다고 생각합시다.
$i$에서 $j$로 가는 것과 $j$에서 $k$로 가는 것을 합쳐주면 $i$에서 $k$로 가는 경우를 구해낼 수 있습니다.
Naive하게 합쳐주면 $O(C^3)$이 걸리지만, knuth optimization 비슷하게 $O(C^2)$에 합칠 수 있습니다.
$(i, a)$에서 $(k, b-1)$로 가는 최적의 경로가 지나는 $j$행의 칸을 $opt(a, b-1)$, $(i, a+1)$에서 $(k, b)$로 가는 최적의 경로가 지나는 $j$행의 칸을 $opt(a+1, b)$, $(i, a)$에서 $(k, b)$로 가는 최적의 경로가 지나는 $j$행의 칸을 $opt(a, b)$라고 하면 $opt(a, b-1) ≤ opt(a, b) ≤ opt(a+1, b)$를 만족합니다.
이 점을 이용해 knuth optimization 비슷하게 행렬을 합쳐주면 $O(C^2)$에 합쳐줄 수 있습니다.
행렬들을 Segment Tree로 관리해주면 시간 제한은 통과할 수 있다. 메모리 제한은 통과하지 못합니다.
메모리 제한을 통과하는 방법은 두 가지정도 알고 있습니다.
- 리프 노드의 범위를 $[x, x]$에서 $[x, x+20]$정도로 바꿔, 일정 범위 밑으로 들어가면 Naive하게 탐색
- $O(\sqrt N)$개씩 버킷 분할
1번 방식으로 하면 원래 복잡도 $O(C^2 log R)$에 상수만 붙는 정도입니다.
2번 방식으로 하면 $O(C^2 \sqrt R)$이지만 코딩이 편해보입니다.
저는 1번 방식으로 했습니다.