データ構造/グラフ
apc001.contest.atcoder.jp 解き方 前提 n個の木を連結にするためには、n-1個の辺を追加する必要がある 条件から辺に含まれる頂点は重複しないので、2n-2個の頂点が辺に含まれる 連結にするためには、各木から少なくとも1つは頂点を選ばないといけない 実装 …
D - People on a Line 解き方 情報をそれぞれ辺としてグラフを作り、DFSしながら条件に当てはまる数字の割当があるかを調べる ハマったところ グラフが連結でないことを想定せず何回かWAした github.com
arc084.contest.atcoder.jp 解き方 +1、*10の2つの計算を辺、自然数を頂点としてグラフを作る 自然数全体を頂点にはできないのでmod Kする コストは各桁の和の変化量(それぞれ1, 0) 01BFSで1 mod Kから0 mod Kまでの最短距離を求める ハマったところ 自然数…
D - Wall 解き方 iを1にするための最小コストをWarshall Floydで求めてから計算 github.com
C - Bridge 解き方 DFSして橋を数える ハマったところ bridgeを見つけるアルゴリズムを忘れていたので、一から書いてたらデバッグに時間かかった github.com
Save your cats | Aizu Online Judge 解き方 pileを頂点、fenceを辺としたグラフを考えると、その双対グラフの最小全域木(コストは、fenceの長さ)を求めれば良い 双対グラフを求めるためには、最短閉路の列挙などする必要があり面倒 元の平面グラフの全域…
D - Restoring Road Network 解き方 これまでに追加した辺のコストの合計と、その辺による各都市間の最短距離(d[i][j])を保持、更新する 距離が小さい方から順に考えていく。 町i, j間の最短距離がcの時、 もし、d[i][j] == cならば、もう辺を追加する必要は…
Mr. Rito Post Office | Aizu Online Judge 解き方 からへの行き方は次の2通り 陸路で行く 船のあるところまで陸路で行き、船で適当なところまで行き、再度陸路 前計算として、陸路での最短距離、海路での最短距離をWarshall Floydで求めておく dp[i][j] = …
Road Construction | Aizu Online Judge 解き方 captalを始点としてdijkstraして、その後経路復元 経路復元のための情報において、条件を満たす辺のなかでコスト最小のものを保存するようにする 多分、priority_queueを使ったdijkstraじゃないとTLEすると思…
Convenient Location | Aizu Online Judge 解き方 Warshall Floydして、町間の最短距離を求め、それが最小となるところを見つける github.com
D - joisino's travel 解き方 すべての町の間の最短経路の距離を事前にWarshall Floyd等で前計算 町の回り方をR!通りすべて試す(R<=8なので間に合う) github.com
arc079.contest.atcoder.jp 解き方 1つ閉路があり、残りはその閉路にぶらさがっているようなグラフ 閉路とそれ以外にまず分ける 閉路以外の部分は、根を0、その上を…としていくと一意に定まる 閉路については、適当に1頂点にxを割り当てて、うまくいくか計算…
http://arc076.contest.atcoder.jp/tasks/arc076_b 解き方 コストの定義を使って,辺の数をO(N)に削減 最小全域木をクラスカルなりプリムなりで求める プリムの場合はpriority_queueを使った実装じゃないと多分間に合わない ハマった所 プリム,クラスカルの…