Evolton
方針
算法をそのまま追う問題である。(1)では から まで、選ばれた が現在の順列に含まれるかを毎回判定して挿入位置を決める。(2)では逆向きに、最大の から順に取り除く。 が順列中にあればその直前の数が選ばれた 、 がなければ先頭に入った数そのものが である。一般の復元算法もこの逆操作を記述すればよい。
解答
(1) 、 なので、最初は である。選ばれた は順に である。
順に操作する。はじめ は空である。 、 のとき、4は に入っていないので4を先頭に入れる。 、 のとき、3は入っていないので である。、 のとき、6は入っていないので である。、 のとき、3は に入っているので、3の直後に8を入れて となる。、 のとき、2は入っていないので である。最後に 、 のとき、5は入っていないので となる。したがって得られる順列は である。
(2)
逆向きに考える。結果が である。最後に処理された は10であるが、10は に含まれていない。したがって最後の操作では、選ばれた が先頭に入れられて消えた形であり、最後の は先頭の8である。8を取り除いて となる。
次に を戻す。9は順列中にあり、その直前は5である。よってこの段階の は5であり、9を取り除いて となる。次に は含まれていないので、先頭の2がその段階の であり、2を取り除いて となる。次に は含まれているが、先頭にあるので、7は「 の直後に入った」のではなく、 自身が先頭に入った場合である。したがってこの段階の は7であり、7を取り除く。 次に は含まれていないので、先頭の5が であり、5を取り除く。 最後に は含まれていないので、先頭の3が である。
以上は後ろから復元した値なので、元の順に並べると である。
(3)
結果として得られた順列を とする。復元は次の手順で行えばよい。 の順に処理する。各段階で、もし が現在の の中にあり、しかも直前に数があるなら、その直前の数をその段階の として記録し、 を から取り除く。もし が に含まれない、または が先頭にあるなら、現在の の先頭の数をその段階の として記録し、その先頭の数を から取り除く。
この操作で得られる の列は後ろからの列なので、最後に逆順に並べれば、(b)で選ばれた数の列が復元される。
別解
解法2（挿入履歴を逆向きにたどる表）
方針
各挿入を「新しい の親を として記録する操作」と見る。
逆向きには最大の から削除すれば、その直前の数、または先頭の数が
一意に元の を与える。
解答
(1)
各段階の順列を表にするととなる。従って である。
(2)
最終順列から の順に逆操作する。逆順に読んで、選ばれた列はである。
(3)
と下げる。現在の で が先頭以外に
あれば、その直前の数を として記録し を削除する。
がない、または先頭にあるなら、先頭の数を として記録し、
その先頭を削除する。最後にの順へ並べ直せばよい。各逆操作は前向き操作のちょうど逆なので、
復元列は一意である。
総評
難度は10段階中5、計算量は10段階中4。目安は15分。順方向の操作は単純だが、 がすでに順列にある場合だけ「 を直後に挿入する」点を丁寧に追う必要がある。逆操作では、大きい から戻すのが自然である。 が先頭にある場合は「直前の数」がないので、 自身が先頭に入った場合として処理する。この例外を明記できるかどうかが復元算法の完成度を左右する。