以下の内容はhttps://kanpurin.hatenablog.com/entry/2021/05/31/041904より取得しました。

ABC203 E - White Pawn

ABC DP高速化典型動的計画法数え上げ競技プログラミング解説

問題はこちら

問題概要

${(2N+1)×(2N+1)}$ のチェス盤があり， ${(0,N)}$ に白のポーンがある．他にも ${M}$ 個の黒のポーンが置かれている．白のポーンは ${(2N,*)}$ の方向に進むとき，白のポーンが ${(2N,Y)}$ に到達できるような ${Y}$ の数はいくつか．

${1\leq N\leq 10^9\\ 0\leq M\leq 2×10^5}$

解説

${dp[i][j]}$ を「 ${(i,j)}$ に到達できるか」とするようなDPを考える．遷移は

${dp[0][N]=True}$
${dp[0][j]=False}$ ( ${j\neq N}$ )
${dp[i][j]=dp[i-1][j-1]\lor dp[i-1][j+1]}$ ( ${(i,j)}$ に黒のポーンがある時)
${dp[i][j]=dp[i-1][j]}$ ( ${(i,j)}$ に黒のポーンがない時)

となる．このままだと ${O(N^2)}$ とかになるが，黒のポーンがある時の遷移を行う回数は ${O(M)}$ 回であり，他の ${dp[i][j]}$ の遷移はDP配列を使いまわすことで無視できる(いわゆるインラインDP)．DP配列の長さが ${O(N)}$ になるが，白のポーンが到達可能な範囲は ${O(\min(N,M))}$ なので削れる．ソートがネックとなり ${O(M\log M)}$

提出プログラム

https://atcoder.jp/contests/abc203/submissions/23081411

感想

DよりEの方が初心者にとっては簡単？

以上の内容はhttps://kanpurin.hatenablog.com/entry/2021/05/31/041904より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます

不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14