問題概要

1 以上 20 以下の整数からなる、長さ $N$ の数列 $A_{1}, A_{2}, \dots, A_{N}$ が与えられる。

この数列の部分列 (連続でなくてよい) であって、任意の整数について、その部分列に含まれる個数が 0 個または 2 個であるものを考える。

そのような部分列に含まれる要素の個数の最大値を求めよ。

制約

$1 \le N \le 2 \times 10^{5}$

考えたこと

「部分列」とあるので、最初は部分列 DP をするのかと考えた。が、良い感じの計算量になる方法は浮かばなかった。というのも「部分列 DP を更新する際に、どの値は既に使ったのか」を管理したいのだ。bit DP ができるなら、したい。

そこで、代わりに次の DP を考えることにした。

dp[S]： $A_{1}, A_{2}, \dots, A_{j}$ から、「整数値集合 $S$ に含まれる整数がちょうど 2 個ずつ含まれる」ような部分列をとれるような $j$ の最小値（とれない場合は $N+1$ ）

この DP を更新するために、以下のデータをあらかじめ用意しておく。これは、 $M = \max(A_{1}, A_{2}, \dots, A_{N})$ として、 $O(MN)$ の計算量で求められる。

nex[i][c]： $A_{j} = c$ となるような $j$ ( $\ge i$ ) の最小値

また、DP の更新に要する計算量は $O(2^{M} M)$ となる。以上をまとめて、計算量は $O(M(N + 2^{M}))$ と評価できる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    const int MAX = 20;
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i], A[i]--;

    // nexind[i][c] := 各文字 c について A[j] = c なる j (>= i) の最小値
    vector nexind(N+1, vector(MAX, N));
    for (int i = N-1; i >= 0; i--) {
        for (int j = 0; j < MAX; j++) {
            nexind[i][j] = nexind[i+1][j];
        }
        nexind[i][A[i]] = i;
    }

    // bitDP
    int res = 0;
    const int INF = 1 << 29;
    vector<int> dp(1 << MAX, INF);
    dp[0] = 0;
    for (int bit = 0; bit < (1 << MAX); bit++) {
        if (dp[bit] == INF) continue;
        res = max(res, __builtin_popcount(bit) * 2);
        for (int v = 0; v < MAX; v++) {
            if (bit & (1 << v)) continue;
            int bit2 = bit | (1 << v);
            int nex = nexind[dp[bit]][v];
            if (nex >= N) continue;
            nex = nexind[nex+1][v];
            if (nex >= N) continue;
            dp[bit2] = min(dp[bit2], nex+1);
        }
    }
    cout << res << endl;
}

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

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

AtCoder ABC 381 F - 1122 Subsequence (2D, 青色, 525 点)

問題概要

制約

考えたこと

コード