かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

ABC223 D - Restricted Permutation

ABC 解説競技プログラミング

問題はこちら

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

問題概要

${(1,2,\dots,N)}$ を並び替えて得られる数列 ${P}$ であって以下の条件を満たすもののうち，辞書順最初のものを求めよ．

${i=1,\dots,M}$ に対し， ${P}$ において ${A_i}$ は ${B_i}$ よりも先に現れる．

${2\leq N\leq 2×10^5\\ 1\leq M\leq 2×10^5}$

解説

ポイント

辞書順最小は前から貪欲
要素の追加と最小値(最大値)の取得/削除は優先度付きキュー

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

ある数 ${X}$ を置くためには ${X=B_i}$ となるすべての ${i}$ について ${A_i}$ が既に置かれている必要があります．

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

f:id:kanpurin:20211117035514g:plain:w300

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

アルゴリズム

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

${C_i=0}$ であるような ${i}$ を優先度付きキューに入れる．
優先度付きキューが空になるまで以下を繰り返す．
- 優先度付きキュー内の最小値 ${m}$ を取り出し ${P}$ の末尾に挿入する．
- ${m}$ が先に置くべき数であるような ${i}$ の ${C_i}$ を ${1}$ 減らす．
- この操作で ${C_i=0}$ になった ${i}$ を優先度付きキューに入れる．
${P}$ の要素が ${N}$ 個なら ${P}$ を，そうでないなら ${-1}$ を出力する．

提出プログラム

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

感想