7K12 blog

猫でも分かるアルゴリズム解説

ABC137 E - Coins Respawn

f:id:tkr987:20200512231643p:plain

https://atcoder.jp/contests/abc137/submissions/11045565

  • 最小値でなく最大値を求める場合、辺コストの符号を逆にしてグラフアルゴリズムに投げる
  • 上記に加え、探索して得られた出力(最小値)の符号を逆にして答えとする
  • 最大値は「符号の反転を2回する」と覚えるとコスパが良さそう
  • 辺を通過する毎にP枚コインが減るので、予め辺のコストをP減らしておく

f:id:tkr987:20200512232748p:plain

まず、辺を通過する毎にP枚コインが減るので E_i=C_i - Pとして予め辺のコストを減らしておく。ただし、最小値でなく最大値を求めるので、辺のコストの符号を逆にする必要がある。結局のところ辺のコストは E_i=-(C_i-P)=P - C_iとなる。

次に、最大値を探索する具体的な処理を考える。辺のコストに負があるのでグラフアルゴリズムはベルマンフォード法を使う。ただし、いくらコインが増加するとしてもゴールに辿り着けなければ意味がないため、ゴールに辿り着けない頂点を集めた「無視する頂点集合」を求めておく。頂点sからtに辿り着けるかどうかはDFSを使って O(max(V, E))で求められる(たぶん)ので、全頂点について調べると O(V max(V, E))になる。隣接リストと無視する頂点集合をベルマンフォード法に渡し、探索して得られた最小値の符号を逆にした値が答え(最大値)になる。

感想: 頂点の到達可能性は今後も役に立ちそうなのでライブラリ化した。