ABC478 F - Min-First Search

最小優先探索

考え方

最良優先探索で、評価を値の小ささにした探索を行うという話。
選ばれる順を考えて根付き木にすると思えば、ある値 $x$ が選ばれるのは、以下の $2$ つが満たされたとき。

となると、$x$ の親が選ばれてから $x$ 自身が選ばれるまで、$x$ より大きい値は決して選ばれない。
逆に順序指定がこの条件を守るように構築すれば、自動的に望んだ順の探索になってくれることは明らか。

つまり、$2$ 番目以降の各値ごと、自分より大きい値が最後に登場したのが自分の何個前か数えればよい。
ただし、自分より大きい値が登場していない場合は、代わりに自分より前にある値の個数を数える。
それらの総積が、根付き木における親の指定方法のパターン数である。

ただし、これを愚直に行うと $O(N^2)$ になるため、何らかの方法で高速化する必要があることに注意。
仮に単調スタックを用いれば $O(N)$ になって、間に合う。
他にもいくつか方法はある。

入力を受け取る。

n: 5
q: {1, 3, 4, 2, 5}

頂点 $1$ を根とし、$2$ 番目以降の値について親の候補数を求める。

直前にある自分より大きい値を高速に求めるため、単調スタックを使う。
スタックには、今後「直前にある自分より大きい値」になりうる値と、その位置を残す。

最初に、$(1,1)$ をスタックに入れておく。

値	処理前のスタック	直前にある自分より大きい値	親候補数	処理後のスタック
$3$	$(1,1)$	なし	$1$	$(3,2)$
$4$	$(3,2)$	なし	$2$	$(4,3)$
$2$	$(4,3)$	$4$	$1$	$(4,3),(2,4)$
$5$	$(4,3),(2,4)$	なし	$4$	$(5,5)$

たとえば値 $2$ では、直前にある自分より大きい値は $1$ 個前の $4$ なので、親の候補は $4$ だけである。

値 $5$ では、それ以前に自分より大きい値がないので、前にある $4$ 頂点すべてが親の候補になる。

したがって、親の指定方法の総数は $1\times2\times1\times4=8$ となる。

答えは $8$ である。

特になし。

特になし。