Report(報告) - joi2011-day3 解説

筆者: qnighy

N人全てにその報告対象がちょうど1名定められていて、それを辿って辿りつける範囲に報告が届くときに、ある時点までに誰が何回報告されたかを計算する問題である。

O(N^2)解法

問題文の指示通りに処理すればよい。これで10点が期待できる。

O(NlogN)解法

まず、このグラフが、サイクルを根とする木の集合であることがわかるだろう。

またそれぞれのサイクルは1つの頂点としてみてよいので、本質的に森であることがわかる。

さて、ここで考えたいのは次のクエリである。

• 自分のいる頂点に1を足す。
• 自分のところまで報告が届くような頂点の値の総和を求める。

このクエリの形は見るからにBITである。

そこで、頂点を根(サイクル)からの深さ優先探索の行きがけ順で並び替えてみよう。すると、良い性質が得られる。

すなわち、その人が受け取ることが出来る報告の報告元が、連続した区間上に存在するようになる。

あとはBITに実装すればよい。これで満点がとれる。