hogecoder

tsutaj 競技プログラミングの記録

Codeforces Round #416 (Div. 2) C: Vladik and Memorable Trip

本番出てた回。ようやく復習できました。

問題概要

原文 → Problem - C - Codeforces

長さ  N の数列があり、 i 番目の要素を  a_{i} と書く。

次のルールに従って区間を選ぶ (複数でも良い、数列全体を被覆するような選び方でなくても良い) とき、選んだ区間の重みの合計を最大化せよ。

  • 区間内に登場する要素  val それぞれについて、  val と同じ値を持つ全ての要素が必ず同一の区間内に含まれていなければならない。
  • 区間の重みは、区間内に登場した数字の集合の XOR である (例えば、 \left[ 2, 5, 2, 3 \right] という区間であれば、区間の重みは  2 \oplus 5 \oplus 3 = 4 となる。)

解説

まず、各値について最左、及び最右のインデックスを覚えておき、これを  l_{val}, r_{val} と表記することにします。

取りたい区間の左端  L を固定して、dp[i] = [0, i) の範囲での重み合計の最大値 なる DP を解くことを考えます。問題文の条件より、取りたい区間の中にある要素のうち、最左のインデックス  l_{a_{cur}} L より左であるものがあれば、その区間は invalid です。逆にそうでない場合、区間の右端  R \max ( R, r_{a_{cur}} ) に伸ばす、すなわち今まで出てきた要素と同じ値をもつ全ての要素を同一の区間内に入れられるまで区間を伸ばしたあと、 DP 配列を更新します。

ソースコード

実装はとても楽です。大正義半開区間

int N, a[5010];
int l[5010], r[5010], dp[5010];

signed main() {
    cin >> N;
    rep(i,0,5010) l[i] = INF, r[i] = -1;
    rep(i,0,N) {
        int p; cin >> p;
        a[i] = p;
        chmin(l[p], i);
        chmax(r[p], i+1);
    }

    rep(i,0,N) {
        chmax(dp[i+1], dp[i]);
        if(l[ a[i] ] == i) {
            int ub = r[ a[i] ], cur = i, val = 0;
            bool ng = false;
            while(cur < ub) {
                if(l[ a[cur] ] < i) ng = true;
                if(l[ a[cur] ] == cur) val ^= a[cur];
                chmax(ub, r[ a[cur++] ]);
            }
            if(!ng) dp[ub] = dp[i] + val;
        }
    }
    cout << dp[N] << endl;
    return 0;
}

問題で要求されている条件のわりに実装が簡単で面白いですね。