2017-06-27から1日間の記事一覧

SRM 716 DIV1 450: JumpDistancesOnTree

まず与えられた木の全点対の距離を計算しておく。 これを d[u][v]: (u, v)間の距離 としておく。 d[u][v] ∈ Sかつu!=v であるような辺(u, v)をすべて持つようなグラフをHとする。このグラフでスタート地点の頂点0から探索して到達可能な頂点の集合をVとする…

SRM 716 DIV1 250: ConstructLCS

ab<=bc<=caを仮定すると下の図のように解を構成できる。 実際はab, bc, caの大小関係はこのとおりとは限らない。なので、ソートしてから3個の文字列を作ってみる。あとはこの3個の文字列がa, b, cのどれに対応するかを全部試して、実際にLCSを計算してみれば…