AGC032 A - Limited Insertion
解法
操作を逆順で見ていき、数字を取り除いていくことを考えます。今現在の数列をで表すと、
となった場合に
番目の数字を取り除くことができます。
この操作を行った場合、番目以降の数字は順番が一つ前になります。
ですが、番目より手前の数字には、何も影響がありません。
加えて、を後ろに送る操作は存在しないので、
となっている要素のうち一番後ろにあるものについて、取り除く操作を常に行っていけばよいことになります。
最終的に空になった場合に、その操作を逆順で見れば、答えとなります。
感想
前回のA問題で痛い目を見たので覚悟をしていましたが、今回は無事はやときすることができました。
後ろから行うことができるという点に気づくことができればこの問題の本質がつかめる…と思います。
