最終更新: 2020-08-27T19:59+0900
解けなかった。まだ解けていない。考慮すべきが漏れてるのか、何か思い違いがあるのか。
とりあえず、完全に並べ替えても題意を満たせないケースに No を返してみた。該当(AC)１件>https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8356932。
N-1 回の交換だと N 要素の A 数列を完全に思い通りに並べ替えられると思った。ぎりぎり１回足りないのが N-2 回なのかな、と。
ぎりぎり１回足りない条件とは？
A 数列のすべての要素があるべき位置から外れた状態にあり、A 数列のすべての要素が数珠つなぎに位置を交換している、だと思った。
ソート済みの A 数列のどの隣接要素を入れ替えても題意を満たせなくなることだと思った。
逆の例は、B 数列に重複する値が存在する場合や、B 数列の最小要素以下の要素が A 数列に複数ある場合など。その場合は A 数列に区別が不要な要素が存在するということであり、交換回数を節約できてしまう気がした。
これもそうではない例を考えると、A 数列が k 要素と N-k 要素の２グループに分かれて位置を交換している場合が該当する。k 要素をあるべき位置に並べ替えるのに k-1 回の交換を要し、N-k 要素を並べ替えるのに N-k-1 回の交換を要するのだから、計 N-2 回の交換で A 数列のすべての要素があるべき位置に納まってしまう。
だから A 数列のすべての要素が唯一のグループを作って位置を交換していなければいけない。その場合に最大 N-1 回の交換を要する。
というのをコードにして提出したのだけど、WA が半分>https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8366469。答えが二択なんだから惜しくもない。わっかんねーなー。