ARC088D Wide Flip

D - Wide Flip

前提

• x を 0 以上 |S|-1 以下の任意の整数とすると、[0,x-1]の区間を反転した後に[0,x]の区間を反転するとS[x]のみ反転させることが可能である。
• K<=|S|より、[0,|S|-1]の反転はKの上限を変化させることなく行えるため、「全ての要素を '0' にする」と「全ての要素を '1' にする」は等価である。

解法

全ての要素を '0' または、全ての要素を '1' とするためには、隣接する要素が異なるような地点を全て解消する必要がある。

S[i]!=S[i+1]となるようなiの集合を P とする。
P の要素 p について考えた時、(S[i]!=S[i+1]となるようなiを新たに増やすことなく) S[p]!=S[p+1]を解消するためには以下の2操作のうちいずれかを行う必要がある。

1. [0,p]の区間と[0,p+1]の区間を反転する
2. [p+1,|S|-1]の区間と[p+2,|S|-1]の区間を反転する

各操作について考えると、①をすると K の上限が p+1 に、②をするとKの上限が |S|-p-2 になる。

Kの上限をできるだけ下げない方を選ぶべきなので、S[p]!=S[p+1]を解消することにより K の上限はmax(p+1,|S|-p-2)となる。P の要素全てにおいてこれを考えると、ans=min{ max(p'-1,|S|-p'-2) | p'∈P }となる。

もう少し考察すると、max(p-1,|S|-p-2)の値はpが中心に近いほど小さくなる。つまり、最も中心に近い p を一つ選び q とおくと、ans = max(q-1,|S|-q-2)としても良い。