整数 \(x\) に対して、\(a(x)\) を \(A_i = x\) となる \(i\) の個数、\(b(x)\) を \(B_i = x\) となる \(x\) の個数とします。

\(A_1 + B_1 = A_2 + B_2 = \dots = A_N + B_N = z\) を満たすようにできる必要十分条件

まず、固定された整数 \(z\) に対して、\(A_1 + B_1 = A_2 + B_2 = \dots = A_N + B_N = z\) となるようにできるための必要十分条件を考えます。最終的に、数列 \(A\) と数列 \(B\) は全て非負になるので、\(z\geq \max\lbrace A_1,A_2,\dots,A_N,B_1,B_2,\dots,B_N\rbrace\) が必要です。以降では、この必要条件が成り立つ場合を考えます。

\(3\) 種類の操作のうち、\(A\) の要素の並べ替えを一番最初に行うものとして良いです。並べ替えた結果、その後 \(A\) と \(B\) に現れる \(-1\) を適切に非負整数に置き換えることによって、\(A_1 + B_1 = A_2 + B_2 = \dots = A_N + B_N = z\) を満たすようにできるための必要十分条件は以下のようになります。

• 各 \(i\) \((1\leq i\leq N)\) について、\(A_i\neq -1\) かつ \(B_i\neq -1\) ならば、\(A_i + B_i = z\) である

\(A\) の並べ替えによって達成可能である、\(A_i\neq -1, B_i\neq -1, A_i+B_i = z\) となるような \(i\) の個数の最大値を \(f(z)\) とします。このとき、\(A\) と \(B\) に現れる \(-1\) の個数の合計が \(N - f(z)\) 以上であるとき、またそのときに限って、前述の条件を満たすように \(A\) を並び替えることができます。

以上より、整数 \(z\) について、\(A_1 + B_1 = A_2 + B_2 = \dots = A_N + B_N = z\) となるようにできるための必要十分条件は以下のようになります。

• \(z\geq \max\lbrace A_1,A_2,\dots,A_N,B_1,B_2,\dots,B_N\rbrace\)
• \(f(z)\geq N - a(-1) - b(-1)\)

また、\(f(z)\) は以下のように表すことができます。

\[ f(z) = \sum_{x=0}^{z}\min\lbrace a(x),b(z-x)\rbrace \]

解法

\(a(x)\geq 1\) となる非負整数 \(x\) は高々 \(N\) 個です。同様に、 \(b(y)\geq 1\) となる非負整数 \(y\) は高々 \(N\) 個です。また、このような \((x,y)\) の組を全て列挙することで、\(f(z)\geq 1\) となる全ての \(z\) について \(f(z)\) を求めることができます。連想配列などのデータ構造を用いることで、全体の計算量は \(\mathrm{O}(N^2)\) や \(\mathrm{O}(N^2\log N)\) となります。