E - Distance Sequence 解説 by en_translator
We solve it with Dynamic Programming (DP).
Let \(\mathrm{dp}[i][j]\) be the number of ways of determining the first \(i\) terms of \(A\) such that its \(i\)-th term is \(j\). The transition of this \(\mathrm{dp}\) is:
\(\mathrm{dp}[i + 1][j] = (\mathrm{dp}[i][1]+\ldots + \mathrm{dp}[i][j - K])+(\mathrm{dp}[i][j + K]+\ldots + \mathrm{dp}[i][M]).\)
Note that the transition is slightly different for \(1 > j - K\) or \(j + K>M\). This DP has \(\mathrm{Ο}(NM)\) states, and computing each element costs \(\mathrm{Ο}(M)\), so the overall time complexity is \(\mathrm{Ο}(NM^2)\), which does not fit in the time limit.
Instead, we may find the cumulative sum of \(dp[i]\) before considering the transitions to \(dp[i+1]\), so that each transition can now be performed in an \(\mathrm{Ο}(1)\) time, so that the problem is solved in a total of \(\mathrm{Ο}(NM)\) time, which is fast enough.
投稿日時:
最終更新: