E - Or Plus Max

問題

長さ $2^N$ の数列 $(A_i)$ (0-indexed)が与えられる。 $k = 1, 2, 3, \dots, 2^N$ に対し、 $\max \{ A_i + A_j \mid i \neq j, \; i \lor j \leq k \}$ を求めよ。

ここで $\lor$ は bitwise or を表す。

制約

• $1 \leq N \leq 18$
• $1 \leq A_i \leq 10^9$

考察

問題の言い換え

$[N] = \{ 0, 1, \cdots, N - 1 \}$ と定める。 また集合 $S \subseteq [N]$ と整数 $\sum_{i \in S} 2^i$ を同一視する。これにより、集合における和集合 $\cup$ と、整数における bitwise or $\lor$ が等価になる。

$k = 1, \dots, 2^N$ に対し、 $\max \{ A_i + A_j \mid i \neq j, \; i \lor j \textcolor{pink}{=} k \}$ の累積 max がこの問題の解となる。よって代わりに以下の問題 A’ を解きたくなる。

しかし $S \cup T = U$ という条件はとても扱いにくい。そこで代わりに $S \cup T \textcolor{pink}{\subseteq} U$ とする。 $S \cup T \subsetneq U$ のケースが入ってしまうが、この場合 $S \cup T \lt U$ なので、どのみち累積 max で取り込まれる。

よって以下の問題 A を解いて、累積 max を取ればいい。 $S \cup T \subseteq U \iff S, T \subseteq U$ に注意。

$A_S + A_T$ を最大化するには、 $A_i$ を大きい方から 2 つ取ってくるのが最善である。つまり問題 A は以下の問題 B に言い換えられる。

問題 B の解法

空でない $S \subseteq [N]$ に対して、 $\{ A_T \mid T \subseteq S \}$ の中で最も大きい要素 2 つを $\mathcal{A}_S$ とする。 $|S| = 1$ の場合は明らかに $\mathcal{A}_S = \{ A_{\emptyset}, A_S \}$ となる。

$|S| \geq 2$ の場合、 $\mathcal{A}_S \subseteq \left( \bigcup_{ i \in S } \mathcal{A}_{S \setminus \{i\} } \right) \cup \{ A_S \}$ となる。 $\left| \left( \bigcup_{ i \in S } \mathcal{A}_{S \setminus \{i\} } \right) \cup \{ A_S \} \right| \leq 2 |S| + 1$ なので、和集合を取ってからソートして上から 2 つ取れば計算量は $O(N \cdot 2^N)$ となる。

実装例

提出 #34675335 - AtCoder Regular Contest 100

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int n;
  cin >> n;

  vector<int> xs(1 << n);
  for (auto& x : xs) cin >> x;

  vector<vector<int>> dp(1 << n);
  int ans = 0;
  for (int s = 1; s < (1 << n); ++s) {
    auto& cands = dp[s];
    cands.push_back(0);
    cands.push_back(s);

    for (int i = 0; i < n; ++i) {
      if ((s >> i) & 1) {
        const auto& childs = dp[s ^ (1 << i)];
        cands.insert(cands.end(), childs.begin(), childs.end());
      }
    }

    // 重複を弾いてから2つに絞る
    sort(cands.begin(), cands.end(), [&](int i, int j){ return xs[i] > xs[j]; });
    cands.erase(unique(cands.begin(), cands.end()), cands.end());
    cands.resize(2);

    ans = max(ans, xs[cands[0]] + xs[cands[1]]);
    cout << ans << "\n";
  }

  return 0;
}