問題
提出コード
解法
基本的に、1つのトランプは1回操作するだけで必ず正しい位置に戻せるので、最悪N回の操作が必要になります。
そして、操作の回数を最小にするには、そもそも操作しないトランプの枚数を最大化すればいいことになります。
これはつまり、できるだけソート済みになっているようにトランプを選び、その他のトランプを挿入していくことになります。この、できるだけソート済みになっている、というのは
のとき
という条件を満たす数列を選び出すときに、できるだけ多くの個数を選ぶ、というものになります。
ということで、LISに帰着させることができました。
LISを利用して部分列が最長になるようなものを選び、それをNから引いたものが、必要最小回の操作回数になります。
