ABC072 D - Derangement

問題
提出コード

解法

となっている部分は、もしくはとスワップをすることで、は条件を満たすことができます。
このとき、実はスワップ先のもしくはも条件を必ず見たします。なぜなら、この数列は順列なので、だった場合は、もしくはがとなり、中身の値がの添え字と異なるからです。
このことを利用すると、前から順番に見ていき、が存在した部分はとスワップする、という操作を繰り返すだけでよいことがわかります。
ただし、だった場合のみ注意が必要で、この場合はとスワップをすれば十分です(この操作により、前の方の最善手が変わることはありません)。