問題文に書かれている手順通りに操作を行いましょう。細かな実装方法にはいくつかバリエーションがあります。

問題文の指示に忠実な実装方法は例えば以下の通りです。

実装例(Python)

手順1と2で配列をそれぞれ調べるのは二度手間です。手順2を一度も行わなかったときに繰り返しを抜けるようにすると例えば以下のようになります。

実装例(Python)

さらに少し考えると、直前に挿入操作を行った続きから調べれることにすれば、配列を一度調べれば十分であることがわかります。

実装例(Python)

手順2で挿入するべき数列の最初の1項だけを挿入することにしても正しく動作します。

実装例(Python)
実装例(C++)

実行時間について

以上の実装では実際に元の数列に数を挿入していますが、多くの言語でこの処理には「挿入位置より後ろに存在する要素の個数」に比例する時間がかかります。このため、最悪の場合に処理全体でかかる時間は、出力する数列の長さを \(M\) として \(\Omega(N^2+M)\) となります。数列に数を挿入するのではなく、答えとなる新たな数列を先頭から順に構築することにすると全体で \(O(M)\) 時間で行うことができます。C 問題以降に挑む際は、処理にかかる計算量を意識するようにしましょう。

実装例(Python) (新たな配列を構築)
実装例(C) (答えの配列を保持せず、逐次出力)