[ABC259 Ex] Yet Another Path Counting

https://atcoder.jp/contests/abc259/tasks/abc259_h

kenkoooo 레이팅: 2406

체감 난이도: P1

Tag: DP, Sqrt Decomposition

---

$N \times N$ 크기의 격자 위에 수 $A_{i, j}$가 쓰여있다. 어떤 칸에서 인접한 오른쪽 칸이나 아래쪽 칸으로 이동할 수 있다.

모든 경로 중, 경로의 시작점과 끝점에 있는 수가 같은 경로의 수를 구해야 하는 문제이다.

---

각 수마다 독립적으로 문제를 해결하려고 시도해보자. 각 수의 등장 횟수를 $S_i$라고 표기한다.

(i) $S_i$가 작으면, $O(S_i ^ 2)$ DP를 이용해 문제를 해결할 수 있다. 

(ii) $S_i$가 크면, $O(N^2)$ DP를 이용해 문제를 해결할 수 있다.

 

두 방법을 적용하는 기준점을 $k$라 하자. (ii)에 해당하는 경우는 $N^2 / k$ 가지이다. 따라서 $O(k^3 + N^4 / k)$ 에 문제를 해결할 수 있고, 조화평균에 따라 $k = N$으로 두는 경우가 최적이다. 따라서 시간복잡도는 $O(N^3)$ 이다.

 

https://atcoder.jp/contests/abc259/submissions/47530510