J - Male and Famale

動的計画法(DP)を考えます。

データ

$dp[i][j][k]:=$ {その状態になるのが可能であるかどうか 0 or 1}
$i:$ 今までに1つ以上のグループを選んだか(0 or 1)
$j:$ $j$個目のグループを見た時
$k:$ $(男性-女性)$ の値

遷移

$dp[i][j][k]$ が $1$ のとき

• $j$個目のグループを選ばなかったとき $: dp[i][j+1][k] = 1$
• $j$個目のグループを選んだ時 $: dp[\mathrm{min}(1,i+1)][j+1][k+(A[j]-B[j])] = 1$

考えられる $(男性-女性)$ の値をすべて網羅するため、$k$ の範囲を $-10000 ～ 10000$ 程にしておくとよいでしょう。

xxxxxxxxxx

n = int(input())

A = list(map(int,input().split()))

B = list(map(int,input().split()))

​

p = 10005

m = 2*p+5

INF = 10**18

dp = [[[INF for k in range(m)]for j in range(n+1)]for i in range(2)]

dp[0][0][p] = 1

​

for i in range(2):

    for j in range(n):

        for k in range(m):

            if(dp[i][j][k]==1):

                dp[i][j+1][k] = 1

                dp[min(1,i+1)][j+1][k+(A[j]-B[j])] = 1

​

ans = INF

for k in range(m):

    if(dp[-1][-1][k]==1):

        ans = min(ans, abs(k - p))

​

print(ans)

​

【別解】

愚直なアルゴリズムとして、たとえば以下のようなものが思いつきます。

S := {}  # 空のset
for a, b <- A, B:  # a, bの各要素をそれぞれa, bとして列挙する。
    T := S  # SをTにコピーする
    T |= { 0 }  # Tに0を入れる
    for t <- T:  # Tの各要素をtとして列挙する。
        S |= { t + a - b }  # Sに t + (a - b) を挿入する
print S.map(abs).min()  # 答えは、ノルムが最小になるようなSの要素

実は、このアルゴリズムは $\mathrm{worst O}(N (\mathrm{sum}(A)+ \mathrm{sum} (B)) \mathrm{log} (\mathrm{sum}(A) + \mathrm{sum}(B)))$時間 で作動します。(任意の集合への任意の要素の挿入は要素数に対する対数時間で行えるとします。)

S に属しうる要素の値が満たす条件として、たとえば以下のようなものが考えられます。

• 下界 $: -(\mathrm{sum}(A) + \mathrm{sum}(B))$
• 上界 $: \mathrm{sum}(A) + \mathrm{sum}(B)$

${ A - B }$ からいくつかの値を重複を許さず選んだとき、総和を 最小 / 最大 化する問題を考えると明らかです。
ゆえに、$S$ に属する元の個数は常に $\mathrm{O}(\mathrm{sum(A)} + \mathrm{sum}(B))$ 個です。

xxxxxxxxxx

#include <iostream>

#include <valarray>

#include <unordered_set>

​

int main() {

  int n; std::cin >> n;

  std::valarray<std::pair<int,int>> ab(n);

  for(auto& [a, _] : ab) std::cin >> a;

  for(auto& [_, b] : ab) std::cin >> b;

  std::unordered_set<int> s;

  for(auto& [a, b] : ab) {

    auto t = s;

    t.insert(0);

    for(int v : t) s.insert(v + a - b);

  }

  int ans = 1 << 30;

  for(int v : s) ans = std::min(ans, std::abs(v));

  std::cout << ans << "\n";

}

​