miscalc のブログ

主に競プロの話をします

miscalc 作問一覧

ABC 寄り？

問題 難易度 コメント
SLASH 100 わかる人には元ネタがわかりそう
Time Bomb Game 250 わかる人には元ネタがわかりそう 2
Strong String 300 初作問
Sum of Slide Max 500
K Consecutive Ks (Easy) 550
FizzBuzz Difference 575 ARC 寄りのつもりで作ったが ABC 寄りらしい
K Consecutive Ks (Hard) 650 ？ 想定解は天才だけど別解があって、現代なら ABC-Ex 程度？

ARC 寄り？

問題 難易度 コメント
→↑↓ 300 自明すぎるかと思ったがそうでもないらしい　A 問題って感じの問題
Sequence 400 ABC 寄りに入れるか迷った　わかる人には元ネタがわかりそう 3
I Want AC 400 ARC-A っぽいのが欲しいと思って B - Postdocs を改造　難易度は ARC-B くらいかも
Flat Permutation 500 散歩してたら生えた　たくさんの fav ありがとうございます
Time Bomb Game 2 500 面倒という意見が多かった（すみません）
Japanese Gift Money 600 元ネタわかりやすいと思ってたら運営陣に全然通じてなかった
Copy and Paste 2 800 自作問で一番好きかも　直前に似た問題が出てアドベコン行きになった
Small RPS Tournament 800 タイトルの元ネタは C - Large RPS Tournament だけど設定が似ているのは F - Random Tournament　AC 数の割にはそんなに難しくない（と思っている）のでぜひ考えてみてください
Odd Insertion 900 当初 ★3 を主張していた（え？）　解法に寄り添って設定をいじる作り方をすると難易度推定を外しやすいですね

競プロで使う Dilworth の定理

大学の授業で Dilworth の定理が出てきたので、この機会に（競プロer 的な視点から）まとめてみたいと思います。

例題 1

atcoder.jp

長さ N の数列 A = (A_1, A_2, \ldots, A_N) がある。 N 個それぞれの整数に対して、色を 1 つ選んで塗る。ただし、次を満たす必要がある：

  • A_i と A_j（ i \lt j）が同じ色で塗られているならば、 A_i \lt A_j

このとき、最小で何種類の色を用いればよいか？ N \leq 10^5

最小パス被覆

A = (2, 4, 3, 6, 1, 5) という例で考えてみましょう。まず、二次元平面上に (i, A_i) をプロットしてみます（横軸が i で、縦軸が A_i です）。

次に、これらをグラフの頂点と考えます。 (i, A_i) に対応する頂点を頂点 i と呼ぶことにします。 i \lt j かつ A_i \lt A_j のとき、 i \rightarrow j の辺*1を張ります。つまり、「左下から右上」なものすべてにその向きで辺を張ります。こうしてできるグラフを G とします。

ここで、この G は DAG（Directed Acyclic Graph：有向非巡回グラフ。閉路が存在しない有向グラフのこと）であり、さらに

  • i \rightarrow j の辺、 j \rightarrow k の辺がともに存在するならば、 i \rightarrow k の辺も存在する

ことに注意です。これは

  • 頂点 i から頂点 j（ i \neq j）にたどり着けるならば、頂点 i から頂点 j への（直接の）辺が存在する

と思ってもいいです（こちらのほうが直感的かも）。この性質のことを、この記事では（後で紹介する半順序集合との対応になぞらえて）推移律 と呼ぶことにします。

このときもとの問題は、「同じ色で塗られている頂点の間には、必ず辺が存在する」という条件を満たすように各頂点に色を塗り、そのうえで使う色の個数を最小化すること、と言い換えられます。たとえば次のように 3 色で塗れて、これが最適です*2。

なお、ここで同じ色で塗られた頂点集合のように、

  • その頂点集合に含まれるどんな異なる 2 頂点の間にも、辺が存在する

という条件を満たす G の頂点集合は、 G の パス と対応します（下図）。ここで G の推移律が効いています。

そう考えると、この問題は「 G の頂点をパスに分割*3するとき、パスの個数を最小化する」問題といえます（パスへの分割を パス被覆、サイズ（パスの数）が最小のパス被覆を 最小パス被覆 といいます）。

最大独立集合

ここで、下図の斜線を引いた頂点について考えます。

斜線を引いた頂点は、どの異なる 2 つについても辺が張られていません。ですから、これらはすべて違う色で塗る必要があります。

なお、この斜線を引かれた頂点の集合のように、

  • その頂点集合に含まれるどんな異なる 2 頂点の間にも、辺が存在しない

という条件を満たす G の頂点集合のことを、 G の 独立集合 といいます。また、サイズが最大の独立集合を 最大独立集合 といいます。上の考察をこの言葉を使って言い換えると、 G が推移律を満たす DAG ならいつでも、次が成り立つといえます。

\begin{align} (G \ の最小パス被覆のサイズ) \geq (G \ の最大独立集合のサイズ) \tag{1} \label{dilworth_geq} \end{align}

Dilworth の定理

実は、\eqref{dilworth_geq} よりも強い主張である次が、 G が推移律を満たす DAG ならいつでも成り立ちます：

\begin{align} (G \ の最小パス被覆のサイズ) = (G \ の最大独立集合のサイズ) \tag{2} \label{dilworth_eq} \end{align}

上の例でいうと、斜線を引いた 3 頂点は違う色で塗る必要があるが、実は全体を塗るのもそれに使った 3 色で事足りる、ということですね。これが Dilworth の定理 です*4*5。証明は、例題 2 のほうで重要になってくるのでいったん後回しにします。

これを使うことで、最小パス被覆問題を、最大独立集合問題に変換できるというわけです。今回の問題では、最大独立集合のサイズは単調非増加部分列の長さの最大値であり、LIS と同様に O(N \log N) で計算できます。

（補足）半順序集合とそのグラフ表現

半順序集合の定義

半順序集合 とは、集合 P *6とその上の二項関係 \preceq の組 (P, \preceq) であって、

  • 反射律：どんな a \in P に対しても、 a \preceq a
  • 推移律：どんな a,b,c \in P に対しても、 (a \preceq b かつ b \preceq c) ならば a \preceq c
  • 反対称律：どんな a,b \in P（ a \neq b）に対しても、 a \preceq b と b \preceq a の両方は成り立たない

を満たすもののことをいいます。気持ち的には、不等号っぽい比較が（定義されていれば）いい感じにできる、という感じだと思えばよさそうです。今回の問題の (i, A_i) も、二項関係 \preceq を

  • (i, A_i) \preceq (j, A_j) \Leftrightarrow i = j または (i \lt j かつ A_i \lt A_j)

で定義したときに、半順序集合をなします。

半順序集合のグラフ表現

上で考えたように、半順序はグラフ（より具体的には、推移律を満たす DAG）で表現できます。ちゃんと書くと、 P の要素に対応する頂点をもつ有向グラフ G であって、

  • a \preceq b（ a,b \in P, a \neq b）のとき、 a に対応する頂点から b に対応する頂点に有向辺が張られている

ものを考えます。このとき、反対称律は G が DAG であることに、推移律は G の推移律に対応します。

半順序集合の言葉での Dilworth の定理

P の部分集合 C が 鎖（chain）であるとは、 C の異なる 2 つの要素をどのようにとってきても、 \preceq による比較が可能であることをいいます。より形式的には、「どんな x,y \in C に対しても x \preceq y または y \preceq x が成り立つ」と書けます。これは G のパスに対応します。

P の部分集合 A が 反鎖（antichain）であるとは、 A の異なる 2 つの要素をどのようにとってきても、 \preceq による比較が不可能であることをいいます。より形式的には、「どんな x,y \in A, x \neq y に対しても x \preceq y とはならない」と書けます。これは G の独立集合に対応します。

有限半順序集合 (V, \preceq) において、

\min(V \ を鎖に分割したときの鎖の個数) = \max(V \ の反鎖のサイズ) \tag{3} \label{dilworth_poset}

が成り立つ、というのが（本当の）Dilworth の定理です*7。これは（当然ですが）上の \eqref{dilworth_eq} に対応します。

グラフで表現したときに推移律を満たす DAG になっている、という思考をするよりも、半順序集合をなしていると捉えるほうが直感的な場面も多いと思ったので、紹介しました。

例題 2

atcoder.jp

文字列 S がある。 S の連続部分文字列のうちで回文であるものをいくつか選びたい。ただし、次を満たす必要がある：

  • 選んだ回文のうち 2 つであって、一方が他方の連続部分文字列であるものが存在してはいけない

このとき、最大で何個の回文を選べるか？ |S| \leq 200

ABC-Ex ではあるものの、ここまでの内容を理解していればそう身構える必要はないと思います。

文字列の集合に対して、一方の文字列が他方の文字列の連続部分文字列である、という二項関係を定義すると、これは半順序集合をなします。よって、文字列の集合として S の連続部分文字列である回文の集合をもってくると、求めるものはその反鎖のサイズの最大値です。これは Dilworth の定理から、鎖に分割するときの鎖の個数の最小値になります。

Dilworth の定理を使う向きが例題 1 と逆になっていますね。

最小パス被覆の、二部グラフの最大マッチングへの帰着

先ほどもみたように、「鎖に分割するときの鎖の個数の最小値」はグラフの言葉でいうと「最小パス被覆」です。実は、DAG の最小パス被覆は二部グラフの最大マッチングに帰着します。

二部グラフとは？ 頂点を 2 グループに分けるとき、「同じグループに属する 2 頂点の間には、辺が存在しない」ようにできるグラフのことです。

グラフのマッチングとは？ グラフの辺をいくつか選ぶ方法であって、「どの頂点も、選んだ辺のうち異なる 2 つ以上の辺の端点になっていることはない」ようなもののことです。このうちサイズ（選んだ辺の数）が最大のものが最大マッチングです。

N 個の頂点 1, 2, \ldots, N をもつ DAG G を、 N 個の左側頂点 1, 2, \ldots, N と N 個の右側頂点 1', 2', \ldots, N' *8 をもつ二部グラフ H に対応させることを考えます。対応のさせ方としては、 G の i \rightarrow j の辺を、 H の i \ – \ j' 間の辺に対応させます。

このとき、

(G \ の最小パス被覆のサイズ) = N - (H \ の最大マッチングのサイズ) \tag{4} \label{pathcover_matching}

が成り立ちます。

この理由を説明します。まず、 G のパス被覆について、

(パス被覆のサイズ) = N - (パス被覆に含まれる辺の数) \tag{5} \label{pathcover_edge}

が成り立ちます。これは、パス被覆に使ったパスのどれについても、

(頂点数) = (辺数) + 1 \tag{6} \label{vertex_edge}

となっているからです。\eqref{vertex_edge} をすべてのパスについて足し上げると \eqref{pathcover_edge} になります。\eqref{pathcover_edge} は、「パス被覆のサイズを最小化することは、パス被覆に含まれる辺の数を最大化することと同じである」とも捉えられます。

次に、 G のパス被覆と H のマッチングは上図のように一対一対応します。つまり、

  • G のパス被覆について、使った辺に対応する H の辺を使ったものは H のマッチングです。

    • パス被覆に含まれる辺について、同じ頂点から出ている 2 辺や、同じ頂点に入っている 2 辺はないため、対応する H の辺についても端点を共有する 2 辺は存在しないことになるからです。

  • 逆に、 H のマッチングについて、使った辺に対応する G の辺を使ったものは G のパス被覆です。

    • マッチングに含まれる辺について、端点を共有する 2 辺は存在しないので、対応する G の辺について、同じ頂点から出ている 2 辺や、同じ頂点に入っている 2 辺はありません。ここで、 G は DAG なので、この辺集合はパス被覆をなします*9。

以上より、\eqref{pathcover_matching} が成り立つといえます*10。

これで、二部グラフの最大マッチングが解ければよいことになったので、この問題が解けました*11。細かい計算量評価はここではしません（気になる方はこちらを見るとよいです）が、少なくとも多項式時間にはなっていることがわかると思います。最大独立集合問題は一般のグラフでは NP-hard なのですが、推移律を満たす DAG という特殊ケースでは Dilworth の定理により多項式時間で解けるようになっている、というのはなかなかすごいことだと思います。

Dilworth の定理の証明

DAG の最小パス被覆が二部グラフの最大マッチングに帰着する、つまり、

(G \ の最小パス被覆のサイズ) = N - (H \ の最大マッチングのサイズ) \tag{3) (再掲}

という事実は、実は Dilworth の定理の証明の根幹の一つになっています*12。他に示すことは次の 2 つです。

(H \ の最大マッチングのサイズ) = (H \ の最小点被覆のサイズ) \tag{7} \label{konig}

(G \ の最大独立集合のサイズ) \geq N - (H \ の最小点被覆のサイズ) \tag{8} \label{mis_vertexcover}

これらが示せれば (G \ の最大独立集合のサイズ) \geq (G \ の最小パス被覆のサイズ) がわかります。\eqref{dilworth_geq}（ \leq のほうが成り立つこと）がすでにわかっているので、それとあわせて \eqref{dilworth_eq}（ = が成り立つこと）がわかります。

グラフの点被覆とは？ グラフの頂点をいくつか選ぶ方法であって、「どの辺についても、その端点の少なくとも一方が選んだ頂点に含まれる」ようなもののことです。このうちサイズ（選んだ頂点の個数）が最小のものが最小点被覆です。

二部グラフでの、最大マッチングと最小点被覆の関係（Kőnig の定理）

(H \ の最大マッチングのサイズ) = (H \ の最小点被覆のサイズ) \tag{7) (再掲}

これは一般の二部グラフで成り立ちます（Kőnig の定理*13 と呼ばれます）。

まず、（二部グラフに限らず）どんなグラフでも、明らかに

(点被覆のサイズ) \geq (マッチングのサイズ) \tag{9} \label{konig_geq}

です。マッチングに含まれる辺について、その端点の少なくとも片方は選ばないと、点被覆になりません。これらの端点は重複して出てこないので（これはマッチングの定義からわかります）、マッチングのサイズと同じだけの個数の頂点は最低でも選ぶ必要があるということです。

次に、最大マッチングのサイズと等しいサイズの点被覆が存在することを示します。これがいえたら、（最小点被覆のサイズは当然この点被覆のサイズ以下なので） (最大マッチングのサイズ) \geq (最小点被覆のサイズ) がいえて、\eqref{konig_geq} とあわせて \eqref{konig} が示せます。

ここで、マッチングに使わない辺を黒、使う辺を橙で塗ることにしたとき、通る辺の色が交互になっているパスを 交互道 といい、交互道の中でも端点がいずれもマッチングに使われていないものを 増加道 といいます。最大マッチングには増加道は存在しません*14。なぜなら、もし存在したら、それに含まれる辺の色をすべて反転させることで、マッチングのサイズを 1 増やせるからです。

さて、最大マッチングをひとつとってきたとき、マッチングに使われていない左側頂点を黄色く塗り、そこから左側から右側へは黒い辺、右側から左側へは橙の辺を使って（言い換えると、黒 → 橙 → 黒 → 橙 → … という交互道を使って）到達可能な頂点を黄色で、到達不可能な頂点を白で塗ることにします。このとき、左側の白い頂点と右側の黄色い頂点をすべて選ぶと、これは点被覆になります。

なぜなら、これが点被覆にならないのは左側の黄色い頂点と右側の白い頂点の間に辺が存在する場合のみ*15ですが、そのようなことは起こらないからです。

  • もし左側の黄色い頂点と右側の白い頂点の間に黒い辺が存在したら、それを使って左側の黄色い頂点から右側の白い頂点に行けているはずなのでおかしいです。

  • もし左側の黄色い頂点と右側の白い頂点の間に橙の辺が存在したら、左側の黄色い頂点に行けているのはおかしいです（マッチングに使われているので最初には黄色く塗られませんから、右側の黄色い頂点から橙の辺を使って来たことになります。このときこの左側頂点を端点とする橙の辺が 2 本あることになってしまいます。マッチングのはずなのでおかしいです）。

この点被覆が、欲しかった「最大マッチングのサイズと等しいサイズの点被覆」です。これは、次のことからわかります。

  • 左側の白い頂点には、それを端点とする橙の辺がある。

    • もしなかったら、その頂点はマッチングに使われていないので最初に黄色く塗られるはずである。

  • 右側の黄色い頂点には、それを端点とする橙の辺がある。

    • もしなかったら、増加道が存在していることになる（マッチングに使われていない左側頂点から、交互道を使って、マッチングに使われていないこの右側頂点まで来たことになるので）。これは、最大マッチングであることに矛盾する。

  • 左側の白い頂点と右側の黄色い頂点を結ぶ橙の辺はない。

    • もしあったら、それを使って右側の黄色い頂点から左側の黄色い頂点に行けているはずである。

これで示せました。

最大独立集合と、二部グラフの最小点被覆の関係

(G \ の最大独立集合のサイズ) \geq N - (H \ の最小点被覆のサイズ) \tag{8) (再掲}

「 G の独立集合であって、サイズが N - (H \ の最小点被覆のサイズ) 以上のもの」が存在することを示します。これが示せれば、最大独立集合のサイズは当然この独立集合のサイズ以上なので、\eqref{mis_vertexcover} が成り立つといえます。これは \eqref{konig} を示すときに使った論法にもよく似ていると思います。

H の最小点被覆について、 G の頂点集合を次のルールで対応させます。

  • 頂点 i も頂点 i' もその点被覆に含まれていないとき、 G の頂点 i を選ぶ。

このとき、選ばれた G の頂点の集合は G の独立集合になっています（もしなっていなかったら、点被覆になっていません）。

この独立集合のサイズは「頂点 i と頂点 i' が、両方 H の最小点被覆に含まれる」ような i の個数によって変わってくるのですが、もしそのような i が存在しなければ、サイズは N - (H \ の最小点被覆のサイズ) に等しいです。

実は、 G が推移律を満たすときは必ずそうなることがわかる*16のですが、別にそうでなくてもいいです。もし「頂点 i と頂点 i' が、両方 H の最小点被覆に含まれる」ような i が存在したら、独立集合のサイズはそのような i の個数のぶんだけ増えます。

よって \eqref{mis_vertexcover} が成り立つことが示せました。

まとめ

例題 1 では、「鎖に分割するときの鎖の個数の最小値」を「反鎖のサイズの最大値」に変換して問題を解きました。この問題の設定において、変換後の問題が LIS という性質がよくて少ない計算量で解ける問題だったので、これが使えました。

例題 2 では逆に、「反鎖のサイズの最大値」を「鎖に分割するときの鎖の個数の最小値」に変換して問題を解きました。こちらは最小パス被覆になり、計算量が（例題 1 の制約では使えない程度には）かかりますが、いつでも二部グラフの最大マッチングを使って（多項式時間で）解ける問題でした。

また、半順序集合を表して得られるグラフ（つまり、推移律を満たす DAG） G と、それにうまく対応する二部グラフ H を考えたときに

  • G の最小パス被覆

  • H の最大マッチング

  • H の最小点被覆

  • G の最大独立集合

がすべて互いに対応する（しかも不等号ではなく等号の関係で！）ということをみました。この関係と、それに用いた仮定をまとめたのが下図です：

参考にしたものなど

*1:頂点 i から頂点 j に向かう有向辺のことをこう書くことにします

*2:ほかにも最適な塗り方はあります

*3:ちゃんと言うと、パスの集合であって、どの頂点もそのうちちょうど 1 つに含まれるようなものです

*4:ちょっと嘘です。本当は半順序集合に対しての定理のことをそう呼んでいる気がします（たぶん）。これについてはこの次の節で触れます

*5:この記事では詳細には触れませんが、似たような定理として Mirsky の定理というのもあります。主張だけ述べると、同じく推移律を満たす DAG G に対して、 (G \ の最長パスの頂点数) = (G \ を独立集合に分割するときの独立集合の数) というもの（と等価）です。最大のものをとってくる側と最小個数で覆う側がちょうど Dilworth の定理と逆転していることがわかると思います。こちらは Dilworth の定理に比べると証明が簡単です

*6:半順序集合の英語 partially ordered set（poset）の頭文字です

*7:こういうふうに、順序の話を先に導入して、後からグラフとつなげる、という流れのことが多い気がします？（あまり知らないので自信なし）この記事では、競プロer はグラフのほうが馴染みがある人が多いと思ったのでグラフの話を先に紹介していました

*8:これ以降、二部グラフの 2 グループを「左側」と「右側」のように呼ぶことにします

*9:入次数が 0 の頂点から始めて、辺が出ているうちは進め続ける、という感じでできます

*10:なお、 G が DAG ではない場合は G のパス被覆から H のマッチングへの対応づけはできますが、 H のマッチングから G のパス被覆への対応づけはできるとは限らないので、 \geq は成り立ちますが \leq は必ずしも成り立ちません

*11:二部グラフの最大マッチングの解法はここでは扱いませんでしたが、たとえば、最大フローに帰着させて求めることができます

*12:実際は、Dilworth の定理を証明するだけだったら \leq だけで OK です

*13:ケーニヒ と読みます

*14:逆に、増加道が存在しないマッチングは最大マッチングである、ということもいえます。証明はたとえば 二部グラフの最大マッチングと増加道 | 高校数学の美しい物語 に載っています

*15:他のパターンは「左の白と右の白」「左の白と右の黄」「左の黄と右の黄」を結ぶ辺の場合で、左の白、右の黄はすべて選ばれているので OK

*16:方針だけ書くと、頂点 i と頂点 i' を両方含む点被覆は、「頂点 i を除いても点被覆である」「頂点 i' を除いても点被覆である」のいずれかが成り立つ、ということがいえます

コスト変化が変なときのダイクストラ法

概要

通常の最短経路問題と違って、辺を通ったときのコストの変化のしかたが変な場合でも、ダイクストラ法で解けることがある。ダイクストラ法を適用できる条件は

  • 「途中のコストをあえて大きくしたほうが最終的なコストが小さくなる」ということが起こらない

  • 「辺を通ったことでコストが減る」ということが起こらない

（通常の）最短経路問題とダイクストラ法

（通常の）最短経路問題は、次のような問題です。

グラフがある。グラフの各辺には 重み とよばれる値が設定されている。 i 番目の辺の重みを d_i とする。

あなたは頂点 s にいる。また、コスト とよばれる値を持っている（最初のコストは 0 である）。「今いる頂点を始点にもつ辺を一つ選び、その辺の終点に移動する」ことを繰り返して、頂点 t に行きたい。ここで、コストが x のとき、 i 番目の辺を選んで移動すると、コストが x + d_i になる。頂点 t に着いたときのコストの値の最小値（これを頂点 s と頂点 t の 最短距離 という）を求めよ。

これは、一般にはベルマン・フォード法で、辺の重み d_i がすべて非負のときはダイクストラ法で解くことができます。

ダイクストラ法についての詳細な解説はこの記事の趣旨から外れるので行いませんが、簡潔に述べると、「『現在最短距離が確定している頂点から 1 回の移動で行くことのできる（最短距離が確定していない）頂点のうち、その移動で行ったときのコストの値が最小となるもの』は最短距離が確定する（これは d_i \geq 0 だからです）ので、それを確定させていく」という感じのアルゴリズムです。詳細についてはこの記事が個人的にわかりやすかった（らしい*1）のでおすすめです。

変な最短経路問題とダイクストラ法

さっきの問題をちょっと変えてみましょう。（変えた部分を赤字で示しています）

グラフがある。グラフの各辺には関数が設定されている。 i 番目の辺に設定されている関数を f_i(x) とする。

あなたは頂点 s にいる。また、コスト とよばれる値を持っている（最初のコストは 0 である*2）。「今いる頂点を始点にもつ辺を一つ選び、その辺の終点に移動する」ことを繰り返して、頂点 t に行きたい。ここで、コストが x のとき、 i 番目の辺を選んで移動すると、コストが f_i(x) になる。頂点 t に着いたときのコストの値の最小値（これを頂点 s と頂点 t の 最短距離 という）を求めよ。

これはダイクストラ法で解けるでしょうか？ 実は、 f_i(x) たちが次の条件を満たすとき、ダイクストラ法で解けます。

  • f_i(x) は x に関して広義単調増加な関数である。つまり、「途中のコストをあえて大きくしたほうが最終的なコストが小さくなる」ということが起こらない。

  • x \leq f_i(x) である。つまり、「辺を通ったことでコストが減る」ということが起こらない。

明らかに、通常のダイクストラ法の f_i(x) = x + d_i, d_i \geq 0 はこの条件を満たしています。

一つ目の条件は、これが成り立っていなければそもそも DP 的な考え方ができなくなります。たとえば XOR などはこの性質を満たしません（最短路ではないですが、たとえば D - Dance で DP するのは噓解法です）。これが原因でうまくいかないとき、場合によっては、頂点に持たせる情報を増やすこと（いわゆる拡張ダイクストラ）で対応できることもあります。

二つ目の条件は、通常のダイクストラ法で d_i \geq 0 であることに対応していて、最短距離をすぐ確定させることの正当性に関わっています*3。

また、二つ目の条件について、より厳しい条件である「コストの増加が 0 または 1」が成り立っているとき、（通常の最短経路問題と同様に）01BFS が正当でもあります。priority_queue が deque になっているだけであり、「最短距離が確定できるところから確定する」という点では結局同じことをしているためです。

具体例

atcoder.jp

N 個の都市と M 個の鉄道がある。 i 番目の鉄道は都市 A_i と都市 B_i を結んでいて、時刻が K_i の倍数になるたびに、双方の都市からそれぞれ他方の都市に時間 T_i かけて移動する電車が発車する。時刻 0 に都市 X から移動を開始できるとき、都市 Y には最速でいつたどり着けるか？

都市を頂点、鉄道を辺、時刻をコストとみればよいです。鉄道を使うとき、その鉄道の中で最も早く出発する電車に乗るのが最適である（同じ鉄道なら、遅く出発する電車にわざと乗っても得しない）ので、 f_i(x) = (x \ 以上の最小の \ K_i \ の倍数) + T_i = K_i \lceil \frac{x}{K_i} \rceil + T_i としてよいです。この関数は二つの条件を満たすので、ダイクストラ法が使えます。

「その鉄道の中で最も早く出発する電車に乗るのが最適」というのが、人によっては非自明と感じるかもしれません。そういうときは、問題設定に忠実に、グラフが無限本の辺をもつことにしてみましょう。つまり、各 1 \leq i \leq N, 1 \leq j に対して、頂点 A_i と頂点 B_i を結ぶ無向辺 (i, j) があるとして、辺 (i, j) には f_{i,j}(x) = (x \ 以上の \ K_i \ の倍数のうち、\ j \ 番目に小さいもの) + T_i という関数が設定されていると考えてみましょう。このとき、この関数は二つの条件を満たします。また、ダイクストラ法のアルゴリズムを考えると、 j \geq 2 のとき辺 (i, j) は結局使われないことがわかります。

類題

H - don't be late（ほとんど同じです）

E - Rush Hour 2（ f_i(x) = \min_{y \geq x, y \in \mathbb{Z}} \{ y + C_i + \lfloor \frac{D_i}{y + 1} \rfloor \} になります。ここから別の考察を要求されます）

F - Pond Skater（この形に落とすまでの考察がちょっと大変です）

ARC のネタバレになりえるので、畳んでいます C - Path and Subsequence

ほかにもありそうな気がします。あったらぜひ教えてください。

まとめ

普通の最短経路問題と少し変えられると、ダイクストラ法が使えるのが見えにくくなりますが、アルゴリズムがなぜ成り立っているのかを考えれば、このように少し違っても適用できることがわかると思います。

*1:昔のツイートで言ってた

*2:ここも自由に変えられると思いますが、あまり本質でないのでこのままにしておきます

*3:ということは一つ目の条件だけが成り立っていればベルマン・フォード法で解けそう？ 出題例を見たことはないですが

個数と総和をもつ DP

概要

「条件を満たすものすべてについてのスコアの総和を求めよ」という形の問題を DP で解けることがある。このときスコアの総和だけをもってもうまくいかなくて、条件を満たすものの個数も同時にもっておく必要がある。

例題

atcoder.jp

N 個の整数 A_1, A_2, \ldots, A_N がある。隣り合う 2 数の間に + または - を入れてできる式のうち、- が 2 回以上連続で登場しないものを「良い式」とよぶ。すべての良い式の値の総和を \bmod 10^9 + 7 で求めよ。 N \leq 10^5

良い式の個数を数える問題

まず良い式の個数を数える問題を考えます*1。前から + と - のどちらを入れるか決めていくときに、「直前が - だったら - は使えない」というルールなので、「どこまで決めたか」「直前が + か - か」を状態としてもてば DP できそうです。つまり

  • 状態 (i, op) := A_i の直前までの入れ方を決めたとき、最後に入れた演算子が op であるような状態

  • dpc[i][j] := j = 0 なら op = +、 j = 1 なら op = - として、状態 (i, op) にする方法の個数*2

とできます。あとは「直前が - なら - は使えない」のルールを考慮して、状態 (i, + ) からは状態 (i + 1, + ) または状態 (i + 1, - )、状態 (i, - ) からは状態 (i + 1, + ) に遷移できることにすればよいです。ということで遷移は

  • dpc[i + 1][0] = dpc[i][0] + dpc[i][1]

  • dpc[i + 1][1] = dpc[i][0]

と書けました。

良い式の総和を求める問題*3

式の値というのは、+ を入れたらスコアに A_i が、- を入れたらスコアに -A_i が加算される、というふうにしたときのスコアだと考えることができます。

個数の問題の遷移をほぼそのまま総和の問題にも適用して

  • dps[i][j] := j = 0 なら op = +、 j = 1 なら op = - として、状態 (i, op) にする方法すべてについてのスコアの総和*4

  • （間違い） dps[i + 1][0] = (dps[i][0] + A_{i + 1}) + (dps[i][1] + A_{i + 1})

  • （間違い） dps[i + 1][1] = (dps[i][0] - A_{i + 1})

としたくなります*5が、これはうまくいかないです。なぜでしょう。

一言でいうと、「たくさんある式を状態にまとめており、本来式の数ぶん足さないといけないのに、状態の数ぶんしか足していないことになるから」です。

たとえば N = 4, (A_1, A_2, A_3, A_4) = (2, 7, 1, 8) のケースで、状態 (2, + )、つまり 2 \ ? \ 7 \ ? \ 1 の部分まで決まっていて、最後が + なので 2 \ ? \ 7 + 1 となっている状態を考えてみましょう。この状態になる方法は 2 + 7 + 1 と 2 - 7 + 1 の 2 つあるので、ここから + を入れることにして状態 (3, + ) に遷移したとすれば 2 + 7 + 1 + 8 と 2 - 7 + 1 + 8 の 2 つを考える必要が出てきます。このとき 8 は 2 回足されていないといけないですね。それなのに、上の間違った遷移では 8 は 1 回しか足されないことになってしまいます。

そこでどうするかというと、良い式の個数も同時に考えればよいです。上の例で 8 を 2 回足すべきだというのは、状態 (3, + ) になる方法の数が 2 つあるからです。つまり、スコアへの寄与をありうるものの個数ぶん足せばよいわけです。ということで

  • dps[i + 1][0] = (dps[i][0] + dpc[i][0] \cdot A_{i + 1}) + (dps[i][1] + dpc[i][1] \cdot A_{i + 1})

  • dps[i + 1][1] = (dps[i][0] - dpc[i][0] \cdot A_{i + 1})

と書けました。

実装例

C++ with ACL です（遷移を読みやすくするために modint を使いました）。

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/modint>
using namespace atcoder;
using mint = modint1000000007;

int main()
{
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++)
  {
    cin >> A[i];
  }

  vector<vector<mint>> dpc(N, vector<mint>(2, 0));
  vector<vector<mint>> dps(N, vector<mint>(2, 0));
  dpc[0][0] = 1; // 最初は - が使えるので、直前が + だったとみることにする
  dps[0][0] = A[0];
  for (int i = 0; i < N - 1; i++)
  {
    // 遷移を直接書いてもよいが、ここではループで書く方法を紹介する
    for (int j = 0; j < 2; j++)
    {
      for (int nj = 0; nj < 2; nj++) // nj は遷移先の j
      {
        if (j == 1 && nj == 1) // - は 2 回連続で使えない
          continue;

        mint a = (nj == 0 ? A[i + 1] : -A[i + 1]); // スコアへの寄与
        dpc[i + 1][nj] += dpc[i][j];
        dps[i + 1][nj] += dps[i][j] + dpc[i][j] * a;
      }
    }
  }
  mint ans = dps[N - 1][0] + dps[N - 1][1];
  cout << ans.val() << endl;
}

期待値の線形性との関連

dpe[i][j] := \frac{dps[i][j]}{dpc[i][j]} *6と定義して、上の遷移を変形してみましょう。すると

  • dpe[i + 1][0] = \frac{dpc[i][0]}{dpc[i][0] + dpc[i][1]} dpe[i][0] + \frac{dpc[i][1]}{dpc[i][0] + dpc[i][1]} dpe[i][1] + A_{i + 1}

  • dpe[i + 1][1] = dpe[i][0] - A_{i + 1}

が得られます（難しい変形ではないはずなので、気になる人は各自やってみましょう）。この式、なんだか「期待値の線形性」っぽいですよね。下の式は本当にそのままな感じがしますし、上の式も \frac{dpc[i][0]}{dpc[i][0] + dpc[i][1]}, \frac{dpc[i][1]}{dpc[i][0] + dpc[i][1]} を、状態 (i + 1, + ) にくる前にそれぞれ 状態 (i, + )、状態 (i, - ) であった確率、と捉えることができそうです。

類題

（このテク単体で解ける問題が探せなかった……。知ってる人いたら教えてください）

ほかのテクと組み合わせるやつ：

まとめ

結局、ありうるものの個数をもっておく必要があったのは、スコアへの寄与が足される回数がありうるものの個数になるからでした。慣れてないとけっこう混乱しそうなので、この dps[\mathrm{state_{new}}] \ \xleftarrow{+} \ dps[\mathrm{state_{old}}] + dpc[\mathrm{state_{old}}] \cdot (スコアへの寄与) の形は典型として捉えておくのがよさそうです。

*1:実は "+" か "-+" を使うと言い換えるとフィボナッチ数であることがわかるんですが、ここではより問題設定に忠実にやります

*2:dpc の c は count の c です

*3:こちらも問題の性質が良すぎるためにもっと楽な見方があります、気になる方は公式解説を見てみましょう。これから説明する解法はより汎用的だと思っています

*4:dps の s は sum の s です

*5:別にならないが？ って人もいるかも

*6:dpe の e は期待値の英語 expected value の e です