裏紙

ほぼ競プロ、たまに日記

CF 811 E - Vladik and Entertaining Flags

問題

Problem - E - Codeforces

問題概要

n \times mのグリッドgがあり、各セルに数字がかかれている。グリッドの美しさを、連結成分の個数と定義する(同じ数字かつ上下左右のいずれかで触れていれば連結とする)。

  • クエリ(l,r): グリッドの左端をl、右端をrで切った時に残る部分の美しさを答えよ。

というクエリがq個与えられるので、それぞれに足して答えよ。

  •  1 \le n \le 10
  •  1 \le m \le 10^5
  •  1 \le g_{i,j} \le 10^6
  •  1 \le q \le 10^5
  •  1 \le l \le r \le m

イデア

SegnentTreeのような考え方で、各segmentに対して次の3つの情報を持たせる:

  • 区間の左端lにおけるグリッドの状態(サイズnの配列)
  • 区間の右端rにおけるグリッドの状態(サイズnの配列)
  • segment内の区間に存在する連結成分の個数

この情報を使うと、隣合うsegment同士のmergeは次のようにできる:

いま、segment A( [l_A , r_A ] , 連結成分の個数CC_A)とsegment B( [l_B , r_B ] , 連結成分の個数CC_B)をmergeするという状況を考える(隣り合うことを仮定するので、 r_A + 1 = l_Bとする)。merge後のsegmentをsegment Cとすると、範囲は当然 [l_A , r_B ] になる。

連結成分の個数についてはCC_A + CC_Bからスタートして、初めは各セルに固有のIDをふっておき、一段ずつ見ていきながらUnionFindっぽくIDを同じものにしていくというのを各段にやると実現できる。別に律儀にUFをする必要はなくて、nは非常に小さいので各段に対してO(n)かけて全体でO(n^2)かかっても間に合う。

以上から、1つのクエリに対してO(n^2 log m)で処理ができることが分かったので、これは十分高速である。

実装(C++)

続きを読む

CF 835 F - Roads in the Kingdom

問題

Problem - F - Codeforces

問題概要

n頂点n辺の無向グラフが与えられる。辺iは頂点u_iv_iを結ぶ長さl_iの辺である。

このグラフのinconvenienceを、「全ての頂点対の最短路のmax」と定義することにする。

このグラフから連結性を保ちつつ1つだけ辺を取り除く時の取り除いた後のグラフにおけるincovenienceの最小値を求めよ。

  • 3 \le n \le 200000
  • 1 \le l_i \le 10^9
  • 多重辺、自己ループは存在しない
  • 1つの辺を除いても、全体の連結性が保たれるような辺が存在することが保証される

イデア

入力の条件から、「1つの辺を除いても、全体の連結性が保たれるような辺が存在することが保証される」ということは、取り除いた後のグラフはn頂点n-1辺で、全体が連結ということになるので、これは木である。つまり、与えられるグラフは木に1本だけ余計な辺を足した形になっていることが分かる。

そして、そのようなグラフではループが1つだけ存在し、それに木をいくつかくっつけたような形になっているとみることができ、今回の問題で取り除く対象にできるのはこのループ内の辺に限られることになる。あとは、このループ内の辺に対して削除対象を動かしながらその時のinconvenienceを高速に計算したい。

また、inconvenienceを考える時に、我々が最小化出来るものは「ループ内の辺を通る」パスについてしか出来ないので、それの最小化を考えることにする(例えば、ループ外に巨大な木がくっついていたら、その木の中同士の頂点が最大をとるペアになりそうだが、これはどうしようもないので考えない)。この最小化を考えて、取り除く辺を決定したら、取り除かれたグラフ上で木の直径を求めれば良い。

以下、考えやすいようにループの大きさをCとして、頂点に通し番号をふってあるものとして考える。ループだけを考えれば良いようにするためにループ内の頂点に次のようなパラメータを持たせる:

  • d_i : 頂点iに対してくっついている木の中の最も遠い頂点との距離

また、次のような値を計算しておく:

  • w_i : 頂点ii+1の間の辺の重み
  • pred_i : 頂点0,1, \ldots , iの間で最も離れたペアの距離
  • sufd_i : 頂点i,i+1, \ldots , C-1の間で最も離れたペアの距離
  • pref_i : 頂点0,1, \ldots , iの間で、頂点0と最も離れた頂点の距離
  • suff_i : 頂点i,i+1, \ldots , C-1の間で、頂点0と最も離れた頂点の距離

これらを事前に計算しておくと、頂点ii+1の間の辺を切った場合のinconvenienceはmax( pref_i + suff_{i+1} , pred_i , sufd_{i+1} )で表せるので、全体でO(n)で求められる。

実装(C++)

続きを読む