数列Bの要素を、

• 先頭に追加する操作で追加された要素(タイプL)
• 元々数列に存在した要素(タイプM)
• 末尾に追加する操作で追加された要素(タイプR)

の3種類に分類します。明らかに、この分類により数列BはLLL…LLMMM…MMRRR…RRと3つの区間に分類されることがわかります。よって、どこがどのタイプなのかは \(O(N^2)\) で完全に決め打てます。以後、これは決め打たれているものとします。

タイプMの要素それぞれについて、その要素が本来Aのどこにあったのか？を考えます。

それぞれの値 \(x\) について、Bに含まれる3つのxがL, M, Rのどれに分類されたかに注目します。例えばL, M, Mに分類された場合、Aに含まれる3つの \(x\) のうち、1つめと3つめがそれぞれBの2つのタイプMの要素と対応するはずだ、ということがわかります。つまり、以下のような対応関係である、ということがわかります。

A: ... x ... x ... x ...
        \          |
          \        |
            \      |
B: ... L ... M ... M ...

これを

M*M
LMM

と書きます。同様に場合分けして考えると、ほとんどすべての場合について一意に定まることがわかります。具体的には

M** ***
LMR LLR これら2つを(1)とする

**M ***
LMR LRR これら2つを(2)とする

M** **M
MRR LLM

MMM
MMM

M*M M*M
LMM MMR

このパターンが全てです。要するに、BがLMRのもの以外は一意です。

Mの要素が本来どこにあったかの対応関係がもし全て定まっていたら、これは遷移可能かどうかに注目します。

まず、自明な条件として

自明な条件1: マッチングどうしが交差してはいけない。つまり\( (a_i \to b_j), (a_k \to b_l)\)というタイプMの対応関係があるならば、\(i < k\) かつ \(j > l\)が成立してはいけない。

自明な条件2: 上記の対応関係以外が存在してはいけない

があります。更に、非自明な条件として

条件3: 対応関係(1)の(左右の一番外側の)要素Xと, 対応関係(2)の要素Yの位置関係が以下のようになっていたら不可能

YX ... YX

という条件がわかります。実は条件1,2,3が必要十分です。十分性は、実際にトポロジカルソートなどを使うと手順が構築出来ることによります。

更に、もし遷移可能ならば全てのM以外の要素をちょうど一度ずつ触るような操作が存在することもわかります。これは明らかに最小回数です。

よって、対応関係が決まればこの問題は解けることがわかりました。しかし、本来は対応関係を決め打てないので、これを考える必要があります。

対応関係を決め打てない理由は、BがLMRに分類された時に

M** **M
LMR LMR

のどちらの対応関係かがわからないのが問題でした。ですが、これをどちらのタイプに割り当てるか、をboolean変数として置くと、実は条件1,3は全て2-SATの条件で書けることがわかります。

以上より、この問題は区間の決め打ちに \(O(N^2)\)、2-SATを解くのに \(O(N^2)\) で、\(O(N^4)\) で解けました。