解説:#6 麻布動物園

## 解法 動物園の各エリアを結ぶ水路は、高さに差があったら一方向のみに、差がなければ双方向に流れます。ここから、低いところから高いところに流れる事はない事が分かります。また、水路を有向グラフとみなす事ができます。 また、あるエリア$A$のみに水源を設置した時に、水が流れるエリアの集合をエリア$A$の流域とします。 この時、$A$でないエリア$B$から、エリア$A$に対して水が流れる場合、エリア$B$の流域は必ずエリア$A$の流域を含む事が考察できます。 $A$から$A$でないエリア$C$に水が流れず、また$C$から$A$にも水が流れない場合、水源を$1$つ設定するだけでは全エリアに水を流すことができず、$A$と$C$それぞれに水源を設定する必要があります。 また$A$と$C$の流域の下流側が合流していても、$A$と$C$のどちらに水が流れていれば下流にも必ず水が流れるので、上流を考えるだけで問題ありません。 よって、エリア$A$の流域とエリア$C$の流域で動物園中をカバーできていれば、水源は$A$と$C$の$2$箇所で十分です。 以上から - 「A.水の流れてこない最上流のエリアを1つ見つける」 - 「B.そこを水源として水を流して、流域にマークをつける」 - 「A.マークのついてない場所から最上流になるエリアを1つ見つける」 - 「B.そこから更に水を流して、マークをつける」 - 「A.マークのついてない場所から最上流になるエリアを1つ見つける」 というシュミレーションA,Bを繰り返す事によって、水源を流すエリアの個数の最小値を求める事ができます。 最上流のエリアを1つ見つけるには、一番標高の高いエリアを探せば良いです。一番標高の高いエリアが他の標高の一番高いエリアと繋がっていた場合でも、1箇所を最上流と設定してシュミレーションすれば問題ありません。 ## 実装の注意 最高点を1つ見つけたあとそこから水が流れるエリアは、幅優先探索で求める事ができます。 ### A部分の実装 最高点を1つ見つけて流域を計算するたびに、その次の最高点を毎回計算すると、水路が1個も繋がっていなかった場合にソート自体に $O(N log N)$ かかり、それを$N$回行うので流域の最高点の検索だけで $O(N^2log N)$ となり間に合いません。これを解消するためには、予め全エリアを高い順にソートしておき、1番高いエリアから順番に調べ、すでにマークがついていれば飛ばす、という処理をすれば良いです。そうすると、最高点の検索に $O(N\ log N)$ 、最小値を計算する際に $O(N)$ で確認できます。 ## B部分の実装 「探索の際に同じ高さのエリアが3つ輪っか状に繋がっている」事を考慮して実装しないといけません。これは探索の際に1度参照したエリアにマークをつける、具体的には長さ$N$のbool配列を用意して、エリア$i$を参照したら配列の$i$番目をtrueにし、また参照の際にtrueだったら探索を打ち切る、という処理が必要です。 ちなみにコンテスト中は用意したテストケースががばがばだったので上の処理を気をつけなくてもWAにはならなかったと思います。しかし、2回目以降の探索の際に流域を1から計算しなおすと「$N$箇所のエリアから1箇所に繋がり、そこから$N$箇所のエリアに繋がる」、という動物園で $O(N^2)$ の探索をすることになりTLEとなります。ちゃんとマークをつけると、全ての水路を1回ずつ見る事になるので、は $O(M)$ で済みます。 以上の部分に気をつけながら実装すれば多分完成します。計算量は $O(N log N) + M)$ です。