Codeforces Round #842 (Div. 2)

　Cまで三完。早めにD捨てていればEをACできたと思うけど、D解けなかったのもまずい。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round #842 (Div. 2)　Dが分からなくて、Eやっと答えがあった。
E 二項係数と包除。一回以下でソートできるときは、左側/右側1/3がソート済みのときから、両側1/3がソート済みのときを除く
二回以下でソートできるときは、中央1/3に1～2*nが何個入るかで場合分けすると二項係数でかける。

— titia (@titia_til) January 5, 2023

D. Lucky Permutation

　解法ツイートを見てAC。グラフの問題だろうと思ったのに、どういうグラフを考えれば良いか分からなくなった。

　頂点を1～n、iからP[i]へ辺が出ているグラフを考えると、いくつかのサイクルで表されたグラフとなる。そして、ソートされたものに戻すためには、それぞれの連結成分について、連結成分数-1回だけかかるので、それらを足し合わせれば良い。

　この問題では、1, 2, 3, 5, 4, 6, 7 のように一ヶ所逆転した部分があるものにしたい。ソートされた状態にした後、もう一回操作すれば作れるのは明らか。

　もっと少ない回数でできるか、というと、「iとi+1が同じ連結成分に含まれる」という箇所があれば一回省略することができる。これは、さっき作ったグラフのiとi+1が繋がっているものを互い違いに付け替えることになり、サイクルが二つに分かれるので操作回数が一回減る。