かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

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の方が初心者にとっては簡単？