ABC 401-500/ABC437E - Sort Arrays - 競技プログラミング用 知識集積所

---

問題

ABC437E

必要知識

B以下レベルの内容は省略

• 深さ優先探索※

考え方

「数列3は、数列1の後ろに2をつける」という情報を、頂点1から頂点3へ向かうコスト2の辺として表現する。
すると、0番からN番までN+1頂点の根付き木になる。
基本的には、この上を各頂点からコストが低い順に見ていく深さ優先探索※でいい。

ただし、同じコストの行先が複数あった場合、それらの直接の子を全て先に調査し、それらの孫は同等に扱って別の子であっても同列に比較してコストが低い順に並べなくてはならない。
（入力例1でいえば、2の後に3をチェックする前に4を見て、2と4の子を両方混ぜてコストが低い順に行かなければならない）

ということで、これに対応するには同等のコストの子につながっている孫を、全て同等の子の中で番号最大の子のところに移動させてしまえばよい。
（入力例1でいえば、3は本来2の子であるが、4の子ということにしてしまう）
これで、あとはコストが低い方（同じコストなら番号が若い方）から順に見ていく深さ優先探索※で、訪れた順を答えるだけで済むようになる。

解答例

解答例

注意点

別解