AtCoder Regular Contest 102 F - Revenge of BBuBBBlesort!
自力AC最高点を更新しました！
解法
まず、操作の性質を考えてみると、以下のようなものが浮かび上がります。
- 一度反転した3項の中央は、その後動かすことはできない
- 一度動かした項を元の位置に戻すことはできない
一つ目を示します。項目を中心に反転させたとします。ここから
項目を動かすには、
項目を中心に反転させる必要がありますが、そのままでは
項目と
項目が反転できる大小関係を満たしません。そこで
項目を中心に反転させることでこれを解消しても、今度は
項目と
項目が反転できる大小関係を満たさなくなります。
二つ目は、一つ目の派生です。一度壊した大小関係は元には戻せません。（人間関係と似ていますね）
一つ目の性質から、その後動かさなくていい項、つまりなる
項目しか反転の中心にできないことがわかります。二つ目の性質から、このような項はむしろ動かしてはなりません。このような項をピボットと呼ぶことにします。さて、ピボットは操作の過程で増えるでしょうか？ たしかに条件を満たす項は増えていきますが、実際にそこを中心とした反転を行うことはできない（動かすことのできない項が必ず隣にある）ため、ピボットは増えないものとしてよいことがわかります。よって、入力は以下を満たす必要があります。
- 任意の
について、
項目のいずれかはピボットである
ここで、項を偶数番目と奇数番目に分けたとき、ピボットを区切りとした連続する非ピボット同士で数をやり取りするしかないため、そのような項のみ取り出します。まず、それらが集合として正しくない場合は弾きます。次にそれらを昇順に並べることを考えます。以下のような必要条件が浮かびます。
つまり、ある2つの項を入れ替えなくてはならないとき、その間にそれらを入れ替えられるピボットが必要という事です。
実はこれは十分条件でもあります。つまり、条件を満たした状態から反転を行っても依然として条件は満たされたままになっています。例えば（
がピボット）のような列において、
を中心に反転を行うと
と
が交換できなくなるように思えますが、よく考えると
より右側に
より小さい項が1つはあるはずであり、元から条件を満たしていません。反転後に条件を満たさなくなるように思えるのはすべてこのパターンであることがわかります。
では、条件を満たしているかどうかを判定する方法を考えましょう。区間と区間
が共通部分を持たないとすると、
か
であるといえます。（非ピボットなので等しいことはない）
よって、非ピボットな項目について、
ならばそれより右にそれより小さい非ピボットがなく、
ならばそれより左にそれより大きい非ピボットがないとき、条件は満たされています。これは、左からの累積
列と右からの累積
列を持っておけば、全体として
で判定することができます。
反省
初めてARC-Fなるものを自力で通し、根気よく考察を進めていけば案外解けなくもないことがわかりました。
思考過程はほぼ解法に書いた通りですが、「項を偶奇で分けてピボットで区切った非ピボットたちが集合として正しくない場合は弾く」あたりが少しだけ違います。（といっても、予めそういうのが弾かれるような条件を考えてあったというだけです（ACコードはそっちの実装になっています））
