ABC223 D - Restricted Permutation

問題はこちら

• 問題概要
• 解説
  • アルゴリズム
• 提出プログラム
• 感想

問題概要

を並び替えて得られる数列であって以下の条件を満たすもののうち，辞書順最初のものを求めよ．

• に対し，においてはよりも先に現れる．

解説

辞書順最小のものを求める問題は，前から最小のものを置いていく貪欲法で解けます．
この問題も同様に前から数字を置いていきます．

ある数を置くためにはとなるすべてのについてが既に置かれている必要があります．

「先に置くべき数」がないようなが置くことができる数となり，置くことができる数のうち最小のものを置いていきます．
ある数を置くと，「先に置くべき数」にあるを考えなくてよくなる(既に置かれた)ので消すことができ，置くことができる(「先に置くべき数」がないような)数が増えていくため，繰り返しこの操作を行ことで解くことができます．
また，置くことができるような数のうち最小のものは優先度付きキューを用いて求めることができます(置くことができる数のリストは要素が増えていき，そのうち最小のものが欲しくなるため)．

実際には，各について「先に置くべき数」にを含むようなのリストも作成しておくと良いです．また，各について「先に置くべき数」のリストを持つのではなく「先に置くべき数」の個数さえ持てば十分です．

アルゴリズム

各についてより先に置くべき数の個数をとします．

1. であるようなを優先度付きキューに入れる．
2. 優先度付きキューが空になるまで以下を繰り返す．
   • 優先度付きキュー内の最小値を取り出しの末尾に挿入する．
   • が先に置くべき数であるようなのを減らす．
   • この操作でになったを優先度付きキューに入れる．
3. の要素が個ならを，そうでないならを出力する．

提出プログラム

https://atcoder.jp/contests/abc223/submissions/27274304

感想