yukicoder No.282 おもりと天秤(2)

C(i)をi番目のコインの重さとする。C(a)<C(b)が分かっているとき頂点aから頂点bに有向辺を張る。このグラフをGと置く。

(i) 出次数が0の頂点が一つのみである場合

出自数0の頂点vがGの頂点集合の中でCを最小とする頂点である。このときvについての大小関係は確定するためvをGから取り除く。

(ii) 出自数が0の頂点が複数ある場合

出自数が0の頂点同士で大小比較を行う。出自数が0の頂点数Mは一回のクエリでceil((M+1)/2)まで減らせるため、O(log(M))回のクエリでGの出自数0の頂点は一つになり (i) に帰着できる。

以上からO(N log (N))で全てのコインの重さの大小関係が確定する。