ある \(A_i\) について、\(A_j < A_i\) なる \(j\) の個数が\(A_i\) 個未満だとする。するとどう並び替えても条件は達成不可である。 逆に、このような \(A_i\) が存在しないならば必ず条件を満たす数列が構築可能である。

\(A\) の最大値 \(X\) を一旦全て \(A\) から取り除き、再帰的に問題を解く。条件より \(X\) を取り除いても数列は \(X\) 個以上残るため、出来た数列の \(X\) 番目の要素の後ろに取り除いた \(X\) を全て挿入すればよい。

なお、この帰納法より、この問題の解は実は一意であることもわかる。

問題は計算量である。上記の手続きを素直に配列で実装すると \(O(N^2)\) 時間となってしまう。

解法1: 平衡二分探索木

力技(だが、追加の考察が不要)な方法は、平衡二分木を利用することである。この手続きで求められる操作は \(k\) 番目への要素の挿入であり、これは平衡二分木ならば \(O(\log N)\) 時間で可能である。よって合計で \(O(N \log N)\) 時間となる。

ただし、( std::set で対応できない)平衡二分木がAtCoderの問題で要求されることは稀であり、この問題も別の解法が存在する。

解法2: stack

先述の構築法は、\(B\) の要素を先頭から一つ一つ確定させていくことを考えると、実は「使用可能な値のうち最も大きなもの」を 追加していく貪欲となっている。よって、この使用可能な値を stack で管理していく、以下の手続きが導かれる。

値 \(x\) の残り個数を \(C_x\) とする。空の数列 \(B\) を用意し、次の手順を \(|B|=N\) となるまで繰り返す。

1. 現在の \(B\) の長さを \(L\) とする。
2. \(C_L\gt 0\) ならば、\(B\) の末尾に \(L\) を一つ追加する。残りの \(L\) はスタックに積み、\(C_L=0\) として、この反復を終了する。
3. そうでなく、スタックが空でなければ、スタックの一番上の値を取り出して \(B\) の末尾に追加する。
4. そうでなく、スタックが空ならば、条件を満たす数列は存在しない。