CF 811 E - Vladik and Entertaining Flags
問題
問題概要
のグリッドがあり、各セルに数字がかかれている。グリッドの美しさを、連結成分の個数と定義する(同じ数字かつ上下左右のいずれかで触れていれば連結とする)。
- クエリ: グリッドの左端を、右端をで切った時に残る部分の美しさを答えよ。
というクエリが個与えられるので、それぞれに足して答えよ。
アイデア
SegnentTreeのような考え方で、各segmentに対して次の3つの情報を持たせる:
この情報を使うと、隣合うsegment同士のmergeは次のようにできる:
いま、segment A(, 連結成分の個数)とsegment B(, 連結成分の個数)をmergeするという状況を考える(隣り合うことを仮定するので、とする)。merge後のsegmentをsegment Cとすると、範囲は当然になる。
連結成分の個数についてはからスタートして、初めは各セルに固有のIDをふっておき、一段ずつ見ていきながらUnionFindっぽくIDを同じものにしていくというのを各段にやると実現できる。別に律儀にUFをする必要はなくて、は非常に小さいので各段に対してかけて全体でかかっても間に合う。
以上から、1つのクエリに対してで処理ができることが分かったので、これは十分高速である。
実装(C++)
続きを読むCF 835 F - Roads in the Kingdom
問題
問題概要
頂点辺の無向グラフが与えられる。辺は頂点とを結ぶ長さの辺である。
このグラフのinconvenienceを、「全ての頂点対の最短路のmax」と定義することにする。
このグラフから連結性を保ちつつ1つだけ辺を取り除く時の取り除いた後のグラフにおけるincovenienceの最小値を求めよ。
- 多重辺、自己ループは存在しない
- 1つの辺を除いても、全体の連結性が保たれるような辺が存在することが保証される
アイデア
入力の条件から、「1つの辺を除いても、全体の連結性が保たれるような辺が存在することが保証される」ということは、取り除いた後のグラフは頂点辺で、全体が連結ということになるので、これは木である。つまり、与えられるグラフは木に1本だけ余計な辺を足した形になっていることが分かる。
そして、そのようなグラフではループが1つだけ存在し、それに木をいくつかくっつけたような形になっているとみることができ、今回の問題で取り除く対象にできるのはこのループ内の辺に限られることになる。あとは、このループ内の辺に対して削除対象を動かしながらその時のinconvenienceを高速に計算したい。
また、inconvenienceを考える時に、我々が最小化出来るものは「ループ内の辺を通る」パスについてしか出来ないので、それの最小化を考えることにする(例えば、ループ外に巨大な木がくっついていたら、その木の中同士の頂点が最大をとるペアになりそうだが、これはどうしようもないので考えない)。この最小化を考えて、取り除く辺を決定したら、取り除かれたグラフ上で木の直径を求めれば良い。
以下、考えやすいようにループの大きさをとして、頂点に通し番号をふってあるものとして考える。ループだけを考えれば良いようにするためにループ内の頂点に次のようなパラメータを持たせる:
- : 頂点に対してくっついている木の中の最も遠い頂点との距離
また、次のような値を計算しておく:
- : 頂点との間の辺の重み
- : 頂点の間で最も離れたペアの距離
- : 頂点の間で最も離れたペアの距離
- : 頂点の間で、頂点と最も離れた頂点の距離
- : 頂点の間で、頂点と最も離れた頂点の距離
これらを事前に計算しておくと、頂点との間の辺を切った場合のinconvenienceはで表せるので、全体でで求められる。