CF345

CF Programming

19位で赤に戻った はじめてCFとTC両方赤になった やったぜ。

Copenした
C:大小関係(のうち最も近いものだけ)でDAGを作り,最短経路を求めればいい.先にunionfindしたけど,よく考えるとSCCすればよかった.
A:同じ点があることに注意して数える
B:片方どこまで行くか固定して,もう片側はにぶたん.絶対バグらせまくると思ったけど割とスムーズに行けた.
D:ドワコンのLISのやつにめっちゃ似ている.動いた点を使わない場合:もとのLISに含まれてない点 もしくは含まれているがそこと同じランク(LISで何番目か)の点が複数あればLISは減らない.そうでなければLIS-1.使う場合:クエリ先読みしておいて,LISを左右から作るとき,該当の場所で実際にそれを追加してみようとすると左右への長さがわかるので求まる.

全部通ってよかった.

あまりレーティングというものを気にしないほうがいいことがわかる

コンテスト後
E:適当に辺を一つ取得できる機能を持つLCTreeでできるっぽいが,実はめちゃくちゃ簡単に出来る.

N頂点の木Aを木Bに変えるとする.最小回数はN-1 - (AとBで一致してる辺の数) になる(これは明らかな下限).これを構成する.
とりあえずA,Bで一致してる辺のみでunionfindする.その後AとBで適当な頂点(同じ)からそれぞれdfsする.dfs(v,p)時に,もしvとpが同じ連結成分(unionfindの話)でなければ(つまり,AにあってBにない辺ならば),「vの連結成分のidから, 辺(v,p)にアクセスできる」ように配列を持っておく.

で,構成だが,Aのdfsの帰りがけ順でAの辺を(必要な物は)外す.今外した辺をv→pとしてvの連結成分のidをvidとおく,その後は,Bの方でvidから(根向きに)生えてる辺をつける(これは一意に存在(∵Aの方とBの方でのunionfindで同じものを同じ頂点とみなした後での根付き木を考えると,頂点集合は同じで根も等しいので)).これでサイクルが出来てしまわないことの証明は次.

帰納法.さっきまでOKだったとして,今あるBの辺を生やした後サイクルが出来たとする.サイクルに各辺がAのものかBのものか書いておいて,Aでの向き,Bでの向きをそのまま入れたものを考えると,ちゃんと有向サイクルになる(∵ある頂点から2本以上辺が出てることがありえないので).さっきまでOKだったので,そのサイクルの内一本にはBと書いてある.ここで,x→y→zという3頂点(2辺)で,「x→yがAかつy→zがB」なるものが存在しないことがわかる(yから生えている辺がBということは既にAでのdfs帰りがけが終了したということで,これはAの子孫xに関してもdfs帰りがけが終了したことを意味する,従ってx→yはAになるはず).このことからサイクル全部の辺がBになるしかないが,これはBが木なことに矛盾.よって(帰納法により)サイクルは出来ない.


結構証明がたいへん(まずあまり成り立つ空気を感じなかった) 全Bにならないといけない,ってとこの議論が面白い.

コード:
A:http://codeforces.com/contest/650/submission/16569600
B:http://codeforces.com/contest/650/submission/16572578
C:http://codeforces.com/contest/650/submission/16567681
D:http://codeforces.com/contest/650/submission/16578322
E:http://codeforces.com/contest/650/submission/16757704

なぜかEの実行時間がめっちゃ遅い O(NlogN)なのに まあNα(N)にすればはやくなるけど