Dまで四完でした。Bで詰まったけど、なんとかDまでいけたのは良かった。
E. What Is It?
$i, j$を置換した結果、iは正しい位置へ来る。なので、swap回数はn-1回。
この条件を満たして$(j-i)^2$が最大になるような置換順を一つ見つければ、最終配置（ソート済み）から遡っていくことで初期配置は求められる。
で、各iについて、j=1かj=nのどちらかで$(j-i)^2$が最大になるので、iがn/2より小さいときはnをペアに、そうでないときは1とペアにすれば良い。
問題文がちょっと分かりにくかったり、出力形式が分かりにくかったり（$p_j=i$となる(i, j)を出力する。(j, i)と逆順に出力してはダメ！）するけれど、実質は簡単でした。
0 件のコメント:
コメントを投稿