ある値が \(A,B\) で合わせて \(N+1\) 個以上出現している場合、鳩の巣原理より答えはNoです。 以下、そうでない場合を考えます。

\(A\) に出現する \(i\) 以下の値の個数を \(C[i]\)、\(B\) に出現する \(i\) 以下の値の個数を \(D[i]\) とします。 \(C,D\) は単調増加で、\(C[i],D[i]\) は \(0\) 以上 \(N\) 以下の整数です。

整数 \(x(0 \leq x \leq N)\) に対して、\(B\) を \(x\) の分だけ右にずらしたもの（元の \(B[i+1]\) の値が新しい \(B[(i+x)\%N+1]\) の値となるようなもの）に候補を絞ります。

\(x\) の条件はすべての \(i(1 \leq i \leq N)\) について三つの区間 \((C[i-1],C[i]],(x+D[i-1],x+D[i]],(N+C[i-1],N+C[i]]\) が互いに重ならないことであり、これは、すべての \(i(1 \leq i \leq N)\) について \(C[i]-D[i-1] \leq x \leq C[i-1]+N-D[i]\) であることに言い換えられます。

そして、そのような \(x\) が常に存在することが示せます。(※1)

上の条件は \(x\) が \(C[i]-D[i-1]\) の最大値以上 \(C[i-1]+N-D[i]\) の最小値以下であるとも言い換えられるので、特に \(x\) が \(C[i]-D[i-1]\) の最大値のとき条件を満たすことがわかります。

よって、\(B\) を \(C[i]-D[i-1]\) の最大値の分だけ右にずらしたものが条件を満たす \(B\) の並べ替えとなり、答えは常にYesになります。 計算量は \(O(N)\) です。

(※1)の証明

ある \((i,j)\) について \(C[i]-D[i-1] > C[j-1]+N-D[j]\) であると仮定して矛盾を導きます。

• \(i \leq j-1\) のとき、\(C[i] \leq C[j-1]\) より \(D[j]-D[i-1] > N\) ですが、\(0\) 以上 \(N\) 以下の整数どうしの差は \(N\) より大きくならないため矛盾。

• \(i-1 \geq j\) のとき、\(-D[i-1] \leq -D[j]\) より \(C[i]-C[j-1] > N\) ですが、\(0\) 以上 \(N\) 以下の整数どうしの差は \(N\) より大きくならないため矛盾。

• \(i=j\) のとき、\(C[i]-C[i-1]+D[i]-D[i-1] > N\) ですが、\(i\) の値が \(A,B\) で合わせて \(N\) 個以下であることに矛盾。

解答例（C++）

また、貪欲法よる計算量 \(O(N)\) の解法も存在します。

解答例（C++）