高速ゼータ変換の練習第二弾！

問題概要

長さ $2^{N}$ の整数列 $A_{0}, A_{1}, \dots, A_{2^{N}−1}$ があります。

$1 \le K \le 2^{N}−1$ を満たすすべての整数 $K$ について、以下の問題を解け:

$i, j$ を $0 \le i$ < $j \le 2^{N}−1$ , $(i or j) \le K$ を満たす整数とするとき、 $A_i + A_j$ の最大値を求めよ。

制約

$1 \le N \le 18$

考えたこと

$2^{N}$ 個の要素を一斉に変換する何かをさせている感じなのでいかにも高速ゼータ変換っぽい。ということで高速ゼータ変換が使える形にすることを考えてみる。

多分だけど、まずは $O(3^{N})$ な bitDP を導いてみるのがよさそうな方向性な気がする。今回はナイーブにやると $O(3^{N})$ どころかもう少しかかってしまいそうである。

dp[ bit ] := 所定の $K = bit$ に対する最大値

とすると、bit の subbit を 2 つ全部調べないといけない錯覚に陥る (1 つで済ませると $O(3^{N})$ )。ちょっと考えるとうまく回避できる。

まず、問題は

$i or j \le K$ となる $(i, j)$

についての走査を要求しているが、なんかちょっと桁 DP を思い出すような扱いづらさがある。これを

$i or j \subseteq L$ となる $(i, j)$

について求めてあげて、それを $L = 0, 1, 2, \dots, K$ について累積 max をとっても同じである。そうすると問題は

dp[ bit ] := bit の subbit のうち A[subbit] が大きい順に 2 個求める (それらを足せばいい)

という風になる。これが「大きい順に 1 個」だったら以下の感じの超典型な高速ゼータ変換だけど、

  for (int i = 0; i < N; ++i) 
    for (int bit = 0; bit < (1<<N); ++bit) 
      if (bit & (1<<i)) 
        chmax(dp[bit], dp[bit^(1<<i)]);

「大きい順に 2 個」でも環であることには変わりないから問題ない。chmax の定義を適切にして、以下のような感じでできる:

#include <iostream>
#include <vector>
using namespace std;

typedef pair<long long, long long> pll;
const long long INF = 1LL<<60;

void chmax(pll &a, pll b) {
  if (a.first < b.first) a.second = max(a.first, b.second), a.first = b.first;
  else a.second = max(a.second, b.first);
}

int main() {
  int N; cin >> N;
  vector<long long> A(1<<N); vector<pll> dp(1<<N);
  for (int bit = 0; bit < (1<<N); ++bit) {
    cin >> A[bit];
    dp[bit] = {A[bit], -INF};
  }
  for (int i = 0; i < N; ++i) 
    for (int bit = 0; bit < (1<<N); ++bit) 
      if (bit & (1<<i)) 
        chmax(dp[bit], dp[bit^(1<<i)]);
  long long res = -INF;
  for (int bit = 0; bit < (1<<N); ++bit) {
    long long tmp = dp[bit].first + dp[bit].second;
    res = max(res, tmp);
    if (bit) cout << res << endl;
  }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ARC 100 E - Or Plus Max (黄色, 700 点)

問題概要

制約

考えたこと