2022-01-07 ABC233 F - Swap and Sort を解いた
ABC233 F - Swap and Sort を解いた。
https://atcoder.jp/contests/abc233/tasks/abc233_f
順列の各要素を頂点・操作対象の要素間を辺とすることは見えた。連結成分内での要素の swap はできるけど、連結成分間では swap できないのでそうなってしまうと -1 になるのも見えた。ただ P を昇順に並べ替える方法とそれが 5 * 10^5 におさまるのかが見えなかった。
解説動画: https://youtu.be/-6clqT8n794?t=1107 解説: https://atcoder.jp/contests/abc233/editorial/3164
連結成分ごとに葉から順に正しい要素へとあわせていく。「葉から順」は dfs して帰りがけ順にすれば良い。さらに各要素ごとに入れ替えるべき要素を dfs して探す。見つからなければその連結成分には存在しないので -1 。最悪の場合は正しい位置に持ってくるのに要素数分の swap なので 1 個目は 999 2 個目は 998 ……となる。
AMAZON ORIGINAL 『シンデレラ』を観た
今日のコミット。