Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど

上手く辺を貼る

コスト0辺のテクニック

この記事は、競技プログラミングでよくあるグラフの問題で、愚直に問題文の指示通りやると辺の数があまりにも多くなりすぎるようなものに対して、コスト0の辺をうまく利用することで辺の数のオーダーを落とす者である。 性質上、すべてのものに適応できるわ…

第二回全国統一プログラミング王決定戦予選-D Shortest Path on a Line

atcoder.jp 概要 最大10^5個の頂点(それぞれ1~Nまで番号を振る)を持つ辺に次の最大10万個のqueryで無向辺を追加する。クエリ LとRとCを与えられる。を満たすすべての(a, b)の間にコストCの辺を張る。クエリを全部処理したのち、頂点1から頂点Nまでの最短経路…