ギガ国の道路事情(GigaCode 2019 [G])

スポンサーリンク

概要

問題文 →
公式解説 →
自分の提出 →

公式解説が読み解けておらず…。

木の圧縮パートを除くと大差ないかもしれません。なかなか実装が大変になってしまいました。

解法

グラフの変形

葉を縮約していきます。葉に接続する辺の寄与は、その両側にいくつの頂点があるかが分かれば計算できるので、それを答に足していきます。

葉に接続する辺の寄与を処理し終わっても、頂点を完全に削除してはダメです。辺を重み 0 のものに置き換えるイメージでしょうか?頂点に対して、いくつの頂点が縮約されたものかを表す重みをもたせます。

この操作の結果、MN の値と連結性は維持されたまま、グラフが次数 1 の頂点を持たない状態になります。

特別な頂点

葉を縮約してしまうと、次数 1 の頂点を持たない連結グラフの場合の計算に帰着されました。残った頂点数が 1 であれば(これは、元が木のとき)、これで計算終了です。

そうでない場合、連結性よりすべての頂点の次数は 2 以上です。次数 3 以上の頂点を特別な頂点として、その個数を K と書きます。

頂点や辺の個数を N,M と書けば、vdeg(v)=2M2(N+777) ですから、次数 3 以上の頂点は高々 2777 個しか存在しません:K2777

なお、N=M のときにはサイクル 1 つが残り、特別な頂点がひとつもなくなります。ひとつ特別な頂点を選んで K=1 として扱えば、以下同じように解くことができます。

グラフ全体としては、特別な頂点 K 個が、O(MN) 個のパスによって互いに結ばれている形になります。これらのパスも列挙しておきましょう。

  • パスは O(MN)
  • パスの長さの和は O(N)

となります。頂点は、「特別な頂点」「パスの内点」の 2 種がありますので、これらで場合分けしながら答を計算していきます。

葉を圧縮した関係で、vw 間の距離に対して重み C[v]C[w] をかけて加算していくといった形の計算を行います。

特別な頂点同士の距離

事前にパスを列挙しておいて、その距離をまとめて計算してしまうことで、Dijkstra 法などにより全点対最短距離が O((MN)2log(MN)) 時間で計算できます。

特別な頂点と、パスの内点の距離の計算

パスの両端点から、注目している特別な頂点までの距離は、事前計算されています。すると、パスの内点から特別な頂点までの距離も、計算できます(パスのどちら側に進むかに応じて、2 通りの min です)。

パスの内点は全部で O(N) 個。特別な頂点は O(MN) 個なので、この部分は全体で O(N(MN)) 時間です。

累積和によって計算量を落とすことも可能です(全体の計算量オーダーには影響しませんが、定数倍改善になるでしょう)。

同じパスの内点同士の距離

同じパスの内点同士であっても、最短路はそのパスの外側を通る可能性があるので、多少厄介です。

パスの長さを n として、i 番目の頂点の重み A[i] と書くと、次の形の計算になります:

  • すべての 0i<jn に対する、A[i]A[j]min{ji,ij+a} の和を求めよ。

これを例えば j を固定して、j ごとに O(1) 時間で計算しましょう。min でどちら側が選ばれるかは i の範囲によって変わり、iA[i](ji)iA[i](ij+a) の形の区間和を計算できればよいことになります。この区間和は、A[i]iA[i] の累積和を計算しておけば O(1) 時間で計算できます。

よって、「同じパスの内点同士の距離」の寄与は、長さ n のパスに対して O(n) 時間で計算できます。すべてのパスを合わせて、このパートは O(N) 時間です。

異なるパスの内点同士の計算

それぞれのパスの長さを、n,m とすると、次の形の計算に帰着されます:

  • 0i<n,0j<m に対して A[i]B[j]min{i+j+a,ij+b,i+j+c,ij+d} の和を求めよ

この係数は、j を決め打てば、min{i+s,i+t} の形です。したがってやはり、A[i]iA[i] の累積和を事前計算しておくことで、j ごとの O(1) 時間で計算できます。

あるパスに対して、相手のパスと j の組をすべて試すと結局 O(N) 通りの計算をすることになり、

ひとつのパスの寄与は O(n+N) 時間です。すべてのパスの組に対してこれを行うと、O(N+(MN)N) 時間となります。


コメント

最近解いた問題:https://atcoder.jp/contests/pakencamp-2018-day2/tasks/pakencamp_2018_day2_g

と似たところが問われている問題。私は本記事の問題の方が、苦戦しました。

どちらも何らかの手法でグラフを圧縮することになりますが、解説の手法?(ちゃんと定義されていないように見えるが、木に追加する辺の端点や、その部分集合の LCA として書ける頂点を特別視かな?)と比べて、私の試みた葉やパスの縮約の方が、頂点数が少なく抑えられているようです。

タイトルとURLをコピーしました