コンテスト中AC:A
A - Larger Score
一応、考察した内容ですが、あまり自信はないです。
番目までの
から順番を保ったまま抜き出した部分列を
、同様に
番目以降の要素から得られる部分列を
とします。
また、任意のを
番目以降に移動させ、任意の
を
番目以内に移動させる操作を入れ替えと呼ぶことにします。
入れ替えに必要な操作回数
と
の入れ替えに必要な最小の操作回数は、
を
番目に移動させた後、
を
番目に移動させればよいので、
が
、
が
とすると、
回となります。
複数個入れ替える場合に必要な操作回数
例えば、である
と、
である
を入れ替える場合を考えます。
この時、と
を入れ替えてから、
と
を入れ替える必要があります。つまり、
番目に近いもの同士から順に入れ替えます。
そうでない場合、操作回数はこれより増えます。
なぜなら、例えば、を先に
番目に移動させると、
は1つ前に出るため、必要な操作回数が1回増えます。
問題の条件を満たすのに必要な操作回数
まず、明らかにを満たすもの1組を入れ替えると達成可能です。
では、複数個入れ替えて最適になる場合があるか考えます。
今、以下と
以上から
個選び、それらが、以下の条件を満たすとします。
ここで、となる組を取り除いても、条件は満たされます。
取り除けるだけ取り除くと、結局、任意の、
について
が成立します。
取り除いた後の個数をすると、前述したとおり、
と
を順に入れ替えしていくのが最適です。
ここで、と
を交換した時点で問題文の条件を満たすので、結局1個だけの交換を考慮するだけでよくなります。
また、であったとします。この時、
かつ
を満たすような
を
の代わりにすると操作回数がより少なくなります。
結局、必要な最小回数の求め方は、について、
と
を入れ替える際に必要な交換回数を求め、その中の最小が答えとなります。但し、
は
かつ
を満たす中で最小のものです。
は、座標圧縮して、Segment Treeで計算しました。
提出コード