naoya_t@hatenablog

いわゆるチラシノウラであります

Educational CodeForces Round 49 (Rated for Div. 2): D - Mouse Hunt

土曜日のABCの後に開催された回。(出てない)

D - Mouse Hunt だけ見た

D - Mouse Hunt

考察

  • 全てのノードからどこかのノード(自分自身を含む)に1本矢印が伸びている、ということはどこかで(あるいは全てが)ぐるぐる回っている。

f:id:n4_t:20180819140503p:plain

  • ぐるぐる部分を見つけて、そのループ内の最安値のノードを塞げばいい
    • 強連結成分分解(SCC)
  • 全てのノードが連結とは限らず、島を形成しているかもしれない。

f:id:n4_t:20180819140510p:plain

  • UnionFindしておくか
  • 1つの島に2つ以上のループが含まれたりとか…しないよね
    • ある島のループ数は必ず1で、島内のどこから出発しても最後にはそのループに陥る

実装

強連結成分分解を島ごとにやる(部分適用)ように蟻本実装を改良して
島ごとの最大サイズの強連結成分をループとみなして、そのループ内の最安値を塞ぐ
→WA
http://codeforces.com/contest/1027/submission/41809297

なぜWA

最後のループが自分自身に向かった矢印だとその強連結成分のサイズは1になってしまうので、最大サイズの強連結成分という拾い方ではうまくいかない。
f:id:n4_t:20180819140556p:plain
強連結成分分解の帰りがけ順の並び(蟻本でいうところのvs[])を使えば良いのでは?
vs[0] には陥ったループの未使用の最後のノードが入っているはず(vs[0]は必ずループに含まれる)
各島について、vs[0] と同じ強連結成分に属するノード(=ループを構成する者たち)の中で最安値を塞いでいく
→AC
http://codeforces.com/contest/1027/submission/41809533

ついでに

強連結成分分解の全体適用/部分適用切り替え可能なクラスを書いてまた通したりもしてみた
http://codeforces.com/contest/1027/submission/41812466

さて

ここまで(自分が)分かりやすいように島ごとに強連結成分分解してたけど、これ蟻本実装のまま一括でやっても同じなのでは?

  • vs[] を左から走査していって、
  • (UnionFindでそのノードのrootを見て)初めて上陸する島ならそのノードがその島のループに属しているに違いない(←どの島もループ部分はvs[] の中で先に来るはずだから)
  • そのノードの強連結成分グループを控えておいて、
  • 控えておいた強連結成分グループごとに最安値を塞いで

→AC
http://codeforces.com/contest/1027/submission/41812874

強連結成分分解の良い練習になった。