全体に \(1\) を足す操作の回数 \(s\) を決め打ったとします． この時，最小の操作回数は二部グラフの重み付き最小完全マッチングとして計算できます．

具体的には，\(A_i \to B_j\) と対応させたい場合，\(A_i\) に施すべき符号反転操作の回数は，以下のように計算できます．

• \(A_i+s \not\equiv B_j \pmod{2}\) の時: 偶奇を考えると，\(A_i\) を \(B_j\) に対応させるのは不可能とわかる．
• \(||A_i|-|B_j|| > s\) の時: \(||A_i|-|B_j||\) の値が操作でどう変化するか考える．符号反転では変わらない．\(1\) 回の全体加算では高々 \(1\) 減少する．よって \(A_i\) を \(B_j\) に対応させるのは不可能とわかる．
• \(B_j-A_i=s\) の時: 明らかに \(0\) 回の符号反転でよい．
• \(-s \leq B_j - (-A_i) \leq s\) の時: \(B_j-(-A_i)=k\) とおくと，\((s-k)/2\) 回全体加算，\(A_i\) の符号反転，\((s+k)/2\) 回全体加算，と操作すれば，\(A_i\) が \(B_j\) に一致する．よって必要な符号反転の回数は \(1\) 回である．
• それ以外のケース: \(1\) 回の符号反転では \(A_i\) と \(B_j\) を一致させることはできないが，\(2\) 回なら必ず可能である．具体的には，最初に符号反転して \(A_i\) を \(-A_i\) で置き換えると，\(1\) 回の符号反転で \(B_j\) に到達できる条件が満たされていることが分かる．

後は全体加算の回数 \(s\) を見積もる必要があります． まず，完全マッチングが存在する最小の \(s\) の値 \(smin\) を求めてみます． これは，\(smin\) の偶奇を \(2\) 種類試し，\(A_i,B_j\) を偶奇で分類して，\(|A_i|,|B_j|\) をソートして貪欲にマッチさせればよいです．

ここで，マッチングの各辺のコストが高々 \(2\) であることに注目すると，解の上界として \(smin+2N\) という値をとることができます．

よって，\(s=smin,smin+1,\cdots,smin+2N\) という \(O(N)\) 個の候補を試せば十分です．

最小重み完全マッチングはハンガリアン法で計算すると \(O(N^3)\) です． よって，全体で \(O(N^4)\) 時間のアルゴリズムでこの問題は解けます．

解答例(C++)