ABC 212 E — Safety Journey

考察

ある都市へ来られる旅の数は、前日の全都市の総和から、来られない都市の分だけ引けば求められる。使える道路が多くても、使えない道路が少ないなら、例外を引く方が速い。同じ都市に留まる移動も禁止なので、その分も忘れずに除く。

まず日数と現在地を状態にする。dpt[v]dp_t[v] を「都市1から出発し、tt 回移動して都市 vv にいる旅の数」と定義する。都市番号は問題文と同じ1始まりとし、1≤v≤N1\leq v\leq N とする。まだ移動していないときは dp0[1]=1dp_0[1]=1、他は0であり、求める答えは dpK[1]dp_K[1] である。以後の計算はすべて法998244353で行う。

素直な遷移では、各到着都市について、道でつながった全出発都市の値を足す。しかし使える道路は最大で N(N−1)/2N(N-1)/2 本あり、毎日走査すると O(KN2)O(KN^2) 時間かかる。入力が列挙しているのは高々5000本の「使えない道路」である。許可された移動を足す代わりに、全体から禁止された移動を引こう。

B(v)B(v) を都市 vv と壊れた道路で結ばれた都市の集合とする。前日の全体和を StS_t とおくと、遷移は次のように書ける。

St=∑u=1Ndpt[u]S_t=\sum_{u=1}^{N}dp_t[u]
dpt+1[v]=St−dpt[v]−∑u∈B(v)dpt[u]dp_{t+1}[v]=S_t-dp_t[v]-\sum_{u\in B(v)}dp_t[u]

第2項は同じ都市に留まる旅、第3項は壊れた道路を使う旅を除く。例えば4都市で、都市2と3の間だけ道が壊れているなら、都市2へ来られるのは都市1と4からだけである。式も St−dpt[2]−dpt[3]=dpt[1]+dpt[4]S_t-dp_t[2]-dp_t[3]=dp_t[1]+dp_t[4] となる。

実装では、前日用の配列を読むだけにして、翌日用の配列を別に作る。

  1. 前日用の配列の総和 StS_t を一度求める。
  2. 全都市 vv の翌日値を St−dpt[v]S_t-dp_t[v] で初期化する。
  3. 壊れた道路 (u,v)(u,v) ごとに、翌日の都市 uu から前日の dpt[v]dp_t[v] を、翌日の都市 vv から前日の dpt[u]dp_t[u] を引く。
  4. 翌日値を法の非負範囲へ戻し、前日用と翌日用の配列を交換する。

これを t=0,…,K−1t=0,\ldots,K-1 の順に行う。毎日、都市と壊れた道路を一度ずつ走査するだけでよい。

典型の発動条件

補集合を使う遷移高速化

許される遷移が多く、禁止される遷移だけが少数列挙されているとき、まず全体の寄与をまとめて足し、例外だけを引く。入力が疎でも、入力された辺が使える辺とは限らない。

ローリング DP

次の日の値が直前の日だけに依存するなら、二つの配列を交換して履歴を省ける。同じ配列を読み書きすると、今日と明日の値が混ざるので注意する。

問題固有の要素

入力された壊れた道路に加えて、自己遷移も禁止されている。問題文の「相異なる都市」を式の −dpt[v]-dp_t[v] に対応付ける。この項は壊れた道路の一覧には現れないので、入力だけを見て遷移を決めない。

正当性

初期値は、移動前に都市1にいる一通りの旅を表す。dptdp_t が tt 回移動した旅を正しく数えると仮定し、翌日の到着都市 vv を固定する。

全体和 StS_t は、前日の各旅を出発都市によらず一度ずつ含む。このうち最後の一歩が許されないのは、出発都市が vv 自身か、集合 B(v)B(v) に属する場合だけである。壊れた道路は異なる二都市を結び、入力に重複もないため、これらを引くと、許可された移動を一度ずつ数えた和になる。

従って遷移後の配列も正しい旅の数を表す。これを KK 回繰り返した dpK[1]dp_K[1] が、都市1へ戻る旅の数となる。

実装上の注意

  • 壊れた道路は双方向なので、両端の翌日値から相手側の前日値を引く。減算の途中でも前日用の配列は変更しない。
  • 減算後は法998244353の非負範囲へ戻す。総和や減算をまとめて計算するなら、途中の値に符号付き64 bit整数を使う。
  • 壊れた道路が0本なら自己遷移だけを除く。全道路が壊れた小入力では、一度移動した後の値はすべて0になる。

復習の核

  • 遷移が多すぎるときは、全体をまとめた後、少ない例外を引けないか考える。
  • 禁止条件は入力された道路だけでなく、問題文の自己遷移禁止まで拾う。
  • 遷移先の値を計算し終えるまで、遷移元の配列を保つ。

計算量と制約

時間

一日につき総和と翌日値の初期化が O(N)O(N)、壊れた道路の両端の減算が O(M)O(M)。入力の読み込みを含め、全体で O(K(N+M))O(K(N+M)) 時間。使える道路を列挙する処理は不要である。

空間

前日・翌日用の二配列に O(N)O(N)、壊れた道路の端点の保存に O(M)O(M) を使い、合計 O(N+M)O(N+M)。日数分の配列は保持しない。

制約との対応

2≤N≤50002\leq N\leq 5000、2≤K≤50002\leq K\leq 5000、壊れた道路は重複のない異なる二都市の組で、0≤M≤min⁡(N(N−1)/2,5000)0\leq M\leq\min(N(N-1)/2,5000) 本である。K(N+M)≤5×107K(N+M)\leq 5\times 10^7 に抑えられる一方、全都市対を毎日調べると KN2KN^2 は最大 1.25×10111.25\times 10^{11} となる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: DP遷移を因数分解・集約して加速する

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

      主タグ: DP遷移の集約・高速化

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

      学習の位置

      体系上の位置: DP遷移を因数分解・集約して加速する

      • 全遷移の総和から禁止辺・禁止keyの集計値を引き、例外の総数で計算量を評価できる。

      先に読む単元:

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

      • 固定線形遷移の巨大回累乗。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題