ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ワーシャル-フロイド法

ABC022 C - Blue Bird

問題 提出コード1 提出コード2 解法 まずは想定解です。 頂点1から出るときの辺と、頂点1に帰るときの辺は違うものでなくてはなりません。 そのときの頂点をとすると、からは純粋な最短経路問題に置き換えることができます。 この問題では、頂点の個数が300…

ABC079 D - Wall

問題 提出コード 解法 1つのマス目が、他のマス目に影響を及ぼすことも、影響されることもないので、それぞれのマスについて、-1でない場合に1へと変化させる魔力の最小値を求めればよいです。 ということで、マス目の現在の数字(0~9)を頂点、をからへ向かう…

ABC074 D - Restoring Road Network

問題 提出コード 解法 まずは、答えが-1、つまり入力された値で条件を満たすグラフを作成できるかどうかの判定をします。 これは、ワーシャルフロイド法を用いて行うことができます。行った結果、すべての距離が更新されることがなかった場合、条件を満たす…

ABC073 D - joisino's travel

問題 提出コード 典型+久々につかう知識問題。 解法 まずは、頂点数が200しかないので、が間に合います。ので、とりあえずワーシャルフロイド法を適用し、それぞれの頂点間の距離の最小値を求めておきます。 そして、通りたい頂点数は8しかないので、全探索…

ABC051 D - Candidates of No Shortest Paths

問題 提出コード 解法 ,を距離で通る辺が使用されるには、との最短距離がになっていればいいです。最短距離になっていない場合、とを通るより最短距離になっているルートを通る方がいかなる場合にも距離が短くなるため、とにおいての最短距離がかどうかだけ…

ABC012 D - バスと避けられない運命

D - バスと避けられない運命 提出コード ワーシャル-フロイド法を利用して、バス停iからバス停jに行くための最短時間をですべて記録します。 終わったら、バス停iについて、そこからバス停jに行くまでの最悪時間を、jで全探索してiごとに記録します。 あとは…

京都大学プログラミングコンテスト(KUPC)2013

競プロの練習会で、こちらのセットを使用したバチャコンをチームで行ったので解いた問題についてのメモをしていきます。 チームメイトはICPC出場時と同じくやまさん(@yamasangamasan)、べるくん(@dora_marutation)でした。加えて、相手チームがICPC本戦出場…