ABC 265 E — Warp

考察

移動の順序をすべて覚える代わりに、三種類の移動を何回ずつ使ったかを覚える。同じ回数組なら現在地も次に選べる移動も一致するので、そこまでの合法な移動列を個数にまとめられる。

各回に三つの選択肢があるため、長さ NN の移動列を全探索すると 3N3^N 通りになる。N≤300N\leq300 では列挙できない。一方、移動量の加算は順序に依存しない。第1・第2・第3移動をそれぞれ (A,B),(C,D),(E,F)(A,B),(C,D),(E,F) とし、nn 回のうちに使った回数を x,y,zx,y,z とすると、現在地 P(n,x,y)=(u,v)P(n,x,y)=(u,v) は

u=Ax+Cy+Ez,v=Bx+Dy+Fz\begin{aligned} u&=Ax+Cy+Ez,\\ v&=Bx+Dy+Fz \end{aligned}

と求まる。ここで x+y+z=nx+y+z=n なので、z=n−x−yz=n-x-y と復元できる。保持する回数は二つでよく、有効な範囲は 0≤n≤N0\leq n\leq N、x,y≥0x,y\geq0、x+y≤nx+y\leq n である。時刻 nn の回数組は O(n2)O(n^2) 個に収まる。

ただし、終点が決まるからといって回数組ごとの並べ方を組合せの式で一括計算することはできない。途中で障害物に着くかどうかは順序によって変わる。そこで、各時点まで障害物を避けた移動列だけをDPで数える。

空の移動列から一回ずつ伸ばす

dp[n][x][y]\mathrm{dp}[n][x][y] を、nn 回の移動がすべて合法で、第1移動を xx 回、第2移動を yy 回使った移動列の個数とする。値はすべて 998244353998244353 で割った余りで持つ。

まだ一度も移動していない空の移動列は一つなので、初期値は dp[0][0][0]=1\mathrm{dp}[0][0][0]=1、それ以外は 00 とする。原点には障害物がないことが制約で保証されている。

n=0,1,…,N−1n=0,1,\ldots,N-1 の順に、有効な各 (x,y)(x,y) について z=n−x−yz=n-x-y と現在地 P(n,x,y)=(u,v)P(n,x,y)=(u,v) を求め、次の三候補を調べる。

選ぶ移動遷移先の状態遷移先の実座標
第1移動(n+1,x+1,y)(n+1,x+1,y)(u+A,v+B)(u+A,v+B)
第2移動(n+1,x,y+1)(n+1,x,y+1)(u+C,v+D)(u+C,v+D)
第3移動(n+1,x,y)(n+1,x,y)(u+E,v+F)(u+E,v+F)

各候補の遷移先の実座標が障害物集合に含まれない場合だけ、その状態へ dp[n][x][y]\mathrm{dp}[n][x][y] を加算する。第3移動では x,yx,y は変わらないが、時刻が一つ進むので復元される zz が一つ増える。ワープなので、二点を結ぶ線分上の障害物を調べる必要はない。

二枚の配列で実装するときは、各時刻の処理前に次層をすべて 00 にし、現在層からの加算を終えてから二枚を交換する。同じ配列をそのまま更新すると、特に第3移動で今回加えた値を再使用してしまう。

最後は終点によらず全状態を足す

この問題には指定された目的地がない。したがって答えは、ちょうど NN 回移動した全状態の和

∑x=0N∑y=0N−xdp[N][x][y]\sum_{x=0}^{N}\sum_{y=0}^{N-x}\mathrm{dp}[N][x][y]

を 998244353998244353 で割った余りである。数える対象は終点の種類数ではなく、移動の順序まで区別した移動列の個数である。

例えば N=2N=2、障害物なしで、三移動を (1,0),(0,1),(−1,2)(1,0),(0,1),(-1,2) とする。第1→第3、第3→第1、第2→第2の三列は、すべて終点 (0,2)(0,2) に着く。最初の二列は同じ回数組 (x,y,z)=(1,0,1)(x,y,z)=(1,0,1) に入り、dp[2][1][0]=2\mathrm{dp}[2][1][0]=2 となる。最後の列は別の回数組 (0,2,0)(0,2,0) に入り、dp[2][0][2]=1\mathrm{dp}[2][0][2]=1 となる。この終点への三列をすべて数え、他の終点への列も足すと答えは 32=93^2=9 である。

同じ例で (1,0)(1,0) に障害物を置くと、第1→第3は初手で禁止されるが、第3→第1と第2→第2は合法である。終点だけを調べても、この違いは分からない。各遷移で着地点を確認することが必要になる。

回数組の違う状態が同じ座標になること自体は問題ない。回数ごとの配列で別々に数えて最後に足せばよい。座標で状態をまとめる別解でも、移動列の個数を加算して保持すれば正しく数えられる。

典型の発動条件

操作種類別回数DP

操作の累積結果が種類ごとの使用回数で決まり、順序を区別して数えたいときに候補になる。合法な履歴を回数組ごとの個数へまとめ、次の操作を一つ追加して伸ばす。途中の条件が現在地だけで判定できることを確認する。訪問済みの点なども後の選択に影響する問題では、回数だけで十分とは限らない。

総和制約による一次元削減

kk 種類の非負回数の和が処理済みの操作数に等しいなら、時刻と k−1k-1 個の回数から残りを復元できる。ただし、有効な範囲を守り、省略した回数だけが増える遷移でも時刻が進むことを忘れない。

問題固有の要素

座標の絶対値は大きいが、障害物は高々 10510^5 点である。平面全体を配列にせず、障害物の座標対をハッシュ集合に保存する。DPは小さい回数の範囲だけを走査し、実座標は着地点が禁止されているか調べるときに復元すればよい。

正当性

各時刻のDPが、それまで一度も障害物に着かず、指定の回数組を使った移動列を過不足なく数えることを示す。時刻0では、原点にいる空の移動列が唯一の合法な列なので、初期値はこの意味に一致する。

時刻 nn までの数え方が正しいとする。同じ状態に入る列は現在地が一致し、次の移動の可否も共通である。各列へ三種類のうち一つを付け足し、着地点が障害物の場合だけ除けば、合法な長さ n+1n+1 の列だけが生成される。逆に、任意の合法な長さ n+1n+1 の列は、末尾の移動とそれを除いた合法な列へ一意に分かれる。従って漏れも重複もなく、遷移後もDPの意味が保たれる。

すべての合法な長さ NN の列は、その使用回数からただ一つの最終状態に属する。異なる順序は同じ状態内でも個数として残り、同じ終点に着く別の回数組もそれぞれ集計される。よって最終層の全状態を足すと求める移動列の総数になる。各加算と最後の集計を法 998244353998244353 で行っても、この総数の余りは変わらない。

実装上の注意

  • 実座標の各成分の絶対値は最大 N⋅109≤3⋅1011N\cdot10^9\leq3\cdot10^{11} になる。乗算前から64 bit整数で計算し、障害物集合の座標対にも同じ型を使う。
  • 障害物は遷移先で判定する。現在地が合法でも次の着地点が合法とは限らない。
  • 現在層と次層の二枚を使い、各時刻で次層を必ず 00 に戻す。第3移動も現在層から次層への更新である。
  • x+y≤nx+y\leq n の範囲だけを走査し、加算と最終層の総和は毎回 998244353998244353 で割った余りにする。

復習の核

  • 選択の順序は膨大でも、種類別の回数だけで現在地と次の選択肢を決められないか考える。
  • 終点が順序に依存しなくても、途中の合法性は順序に依存しうる。合法な列だけを一回ずつ伸ばす。
  • 状態をまとめるときも数える対象の多重度は残す。終点の重複を消すことと、移動列を数えることは違う。
  • 答えが一つの状態とは限らない。終了条件を満たす状態の集合を確認し、今回は最終層全体を足す。

計算量と制約

時間

障害物集合の構築に期待 O(M)O(M) 時間かかる。時刻 nn の有効な回数組は (n+1)(n+2)/2(n+1)(n+2)/2 個で、各状態から三つの候補を調べる。ハッシュ集合への照会を期待 O(1)O(1) とすると、全時刻の遷移は期待 O(N3)O(N^3) 時間である。各時刻の次層クリアの合計も O(N3)O(N^3)、最後の集計は O(N2)O(N^2) なので、全体は期待 O(N3+M)O(N^3+M) 時間となる。公式解説の平衡二分探索木による集合を使う場合は、構築と照会に対数因子が付き、全体は O((N3+M)log⁡(M+2))O((N^3+M)\log(M+2)) 時間となる。

空間

現在層と次層にそれぞれ O(N2)O(N^2)、障害物集合に O(M)O(M) の領域を使い、全体で O(N2+M)O(N^2+M)。全時刻のDPを保存する必要はない。

制約との対応

公式制約は 1≤N≤3001\leq N\leq300、0≤M≤1050\leq M\leq10^5。三つの移動ベクトルは相異なり、各成分と障害物座標の絶対値は 10910^9 以下である。障害物同士は異なり、原点には障害物がない。遷移元となる有効状態の総数は、N=300N=300 で ∑n=0299(n+1)(n+2)/2=4,545,100\sum_{n=0}^{299}(n+1)(n+2)/2=4{,}545{,}100 個なので、三候補ずつ処理できる。

N=1N=1 なら、三つの初手のうち着地点が禁止されていないものの個数が答えになる。障害物がなければ各回に三つを自由に選べるため、答えは 3N mod 9982443533^N\bmod998244353。三つの初手がすべて禁止されていれば第1層がすべて 00 になり、以降も 00 のままなので答えは 00 になる。移動量が (0,0)(0,0) の場合も一回の移動として次層へ進み、原点が禁止されていないため特別扱いは要らない。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Warp の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 最小十分状態からDPを設計する

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: DPの最小十分状態

      執筆: abc-explanation-author1.1.1 / revision 3

      学習の位置

      体系上の位置: 最小十分状態からDPを設計する

      • 採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。

      この解説で扱わないこと:

      • 状態の再利用をせず、頂点を一度ずつ訪問する到達可能性探索。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題