これを解説ACしました。
連続部分列に関する条件が複数与えられ、条件を満たす順列を構成する問題。
条件をよく見ると、一番右の数字は1度しか登場しないことがわかる。・・・(1)
条件を更新していきながら構築をしていくとできそうだけど、実はできない。
なぜなら、一番左の数字も一度しか現れない場合が存在するから。
ところで、一番左の値を固定すると構築できる配列は一意に定まる。
条件を満たす配列は必ず (1) の条件を満たすので、左端を固定して構築を行うと与えられた条件を満たす順列を構築できる。
構築し終わった後に与えられた条件を満たすかのチェックは必須 (条件を満たさずに最後まで構築を行うことが可能なため)。
提出コード
