2 1 4 3 という順列は前半後半の２グループに分かれていて、１回のスワップで達成できる辞書順最小は 2 3 4 1 なので、1 と 3 をスワップする必要がある。何をどう判断して 1 と 3 をスワップすることができるのか。さっきのルールでは 4 を見ているときに 1 を引っぱってくることになって良くない。グループの末尾の位置にあっては多少の妥協をして現在の要素より大きい値を引っぱってくることになっても他所のグループとスワップをしなければいけない。それで 1 を見ているときに 3 を引っぱってくることができる。そうした結果が本当に辞書順最小かというのは実はよくわからないところだけど……。■提出 #46663066 (TLE×18) のち 提出 #46665195 (AC / 772 ms)。アルゴリズム的な違いはない。スワップ候補というのは１度に２つだけ準備できていればいい。最小の要素を持つグループと、２番目に小さい要素を持つグループ。現在見ている要素と異なるグループが実際のスワップ対象になる。この２つの要素を配列の外に出して変数で参照するようにしたりして配列参照を減らしたら TLE が AC になった。■グループの管理とスワップ候補の管理を同時に行うために、UnionFind のルートの決め方をいつものようにサイズの大きい方を新しい代表にするのではなく、値が小さい方を新しい代表にしている。そうすると Find 関数での書き換え回数が増えてまずい場合があるのだけど、代表と最小要素を別々に管理するのは煩雑でミスが避けられない雰囲気だったのでそうしている。スワップ候補の列について。最初にソートして用意するんだけど、スワップ１回につき１つの候補が列から消えることになる。現在見ている要素の代表が消える場合もあり必ずしも先頭２要素のどちらかが消えるとは言えないし、Ruby には SortedSet がない。今から BIT を持ち出すのは大仰で気が進まないし、消す操作を配列に対して素直に行うと実行時間が足りないので、スワップ候補の先頭２要素についてだけ今もまだスワップ候補(グループの代表)のままであるかチェックをするようにして、結果的に削除操作を遅延させている。こういう部分であるとか、数列を先頭からひとなめするだけで辞書順最小を達成するだとかいう部分があるから、効率良くやるのがたいへんな問題だったと思う。スワップするためには最小の要素がどこにあるかを知る必要があって、それを追跡する逆引き配列を予め作成してスワップの際には同時に更新しもしている。たいへんだなあ。そのときそのときで全体を見て最適な選択ができたならもうちょっと簡単だった。■昨日のコンテスト成績証。解くべき問題を解いて -5。まあ順当。B 問題が解けたのえらかったと思う。約分なんて高等数学テクニックとか式をにらんでの２の素因数探しとか、そんなんもう何十年も前に忘れてんねん。■■■「そうした結果が本当に辞書順最小かというのは実はよくわからないところだけど……」。この問題の設定においては位置と値が等価だということをよく考えれば納得できるのではないかな。「グループの末尾の位置にあっては多少の妥協をして現在の要素より大きい値を引っぱってくることになっても他所のグループとスワップをしなければいけない」と書いたけど、この「グループの末尾の位置」というのは必ず１を含むグループの末尾のことだし、「他所のグループ」というのは必ず全メンバーが後方を占めているグループのことなので、そういう関係を踏まえればスワップの位置づけがわかる。いや……、考えれば考えるほど「必ず１を含むグループ」であるということが俄には承服しがたいな。やっぱりそうだと思うんだけど。