Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【Codeforces #590 (Div 3) E Special Permutations】数字を先頭に持っていくと何が変わるのか?

良い問題だと思いました。自分の理解と遠くて、エディトリを読むのに苦労した。所要時間1時間以上(IQ30)

図解してまとめます。

Problem - E - Codeforces

問題

Piをi,1,2,3,4,...i-1,i+1,...Nという順列とする。(iを頭に持っていったやつ)

長さMの数列X(要素 1<=Xi<=N)が与えられる。

この時、順列Piについて、 \sum |pos(Xi) - pos(Xi+1)|を求めなさい。

方針

P1(1,2,3...と整列してるやつ)からiを頭に出した時の差分を計算することにします。XiとXi+1によって作られるセグメントのパターン分けをします。

f:id:akiradeveloper529:20191007205702j:plain

1番のパターン:あるXiとXi+1のセグメントがもしiを含んでいれば(端点は除く)、1減ります。(なぜならば、iが前に行ってしまうため、長さ1現象するから)つまり、こういうパターンについては、iを含むやつが何個あるかわかればよいということになります。この計算は、以下のような端点で+1,-1にしてからcumsumするテクニックが使えますし、別にセグメントツリーでも良いと思います。

f:id:akiradeveloper529:20191007210044j:plain

2番目と3番目のパターン:どっちかの端点がiです。これは、「iとXi」の場合でいうと、iとXiの長さが消滅して、頭からXiの長さが加わるということになります。もう片方もほぼ同じですが、もともとXiの右側にあったやつが左側に行くので、+1の補正が必要です。この計算は、X中のあらゆる隣接関係について、iと隣接してるやつをadj[i]として持つとすれば良いです。明示的に2番と3番を区別するなら、位置関係で分けてL,Rとかでも構わないと思います。