紙コーダー未満

主に競技プログラミングについてです。Topcoder(togatogah)、Codeforces(togatoga)に参加してます。

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

問題

codeforces.com

解法

dp[pos] = [左端がposの時の最大値]とするdpで解いた。
あらかじめ各Aの要素に対して、出現する左端と右端のindexを記録をしておく。
posの値が保存されている要素の左端なら右端の区間まで覆うことができる。
但し同一要素は同一区間に必ず含めるという制約があるため、区間を覆う時に以下の点で注意が必要である。

  1. 区間のある要素の左端のindexが覆う区間の左端より小さいなら、同一要素は同一区間に必ず含めるという条件に矛盾
    例) 1,[2,3,1,2] は条件に矛盾 何故なら1が同じ区間に含まれなくなってしまうため

  2. 同一要素は同一区間に必ず含めるため、出現した要素の右端のindexまで覆う区間を伸ばす必要がある
    例) [2,1,3,2],1なら、[2,1,3,2,1]まで遷移をする時に右端を伸ばす

提出コード

Submission #27384664 - Codeforces

O(n^{2})

コード

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

// c++11
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>

#define mp make_pair
#define mt make_tuple
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

const int INF = 1 << 29;
const double EPS = 1e-9;
const ll MOD = 1000000007;

const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
const int MAX_N = 6010;
int N;
int dp[MAX_N];
bool check[MAX_N];
vector<int> A;
int right_idx[MAX_N];
int left_idx[MAX_N];
int memo(int pos) {
  if (pos >= N) {
    return 0;
  }
  int &res = dp[pos];
  if (res >= 0) {
    return res;
  }
  res = 0;
  res = max(res, memo(pos + 1));

  int val = A[pos];
  int left = left_idx[val];
  int right = right_idx[val];
  // match
  if (pos == left) {
    int xor_val = 0;
    memset(check, false, sizeof(check));

    bool ok = true;
    for (int i = pos; i <= right; i++) {
      if (val != A[i]) {
        int tmp_left = left_idx[A[i]];
        int tmp_right = right_idx[A[i]];
        if (tmp_left < pos) {
          ok = false;
          break;
        }
        right = max(right, tmp_right);
      }

      if (not check[A[i]]) {
        xor_val ^= A[i];
        check[A[i]] = true;
      }
    }
    if (ok) {
      res = max(res, memo(right + 1) + xor_val);
    }
  }
  return res;
}
int main() {
  cin >> N;
  A.resize(N);
  for (auto &val : A) {
    cin >> val;
  }
  for (int i = 0; i < MAX_N; i++) {
    left_idx[i] = INF;
    right_idx[i] = -INF;
  }
  for (int i = 0; i < N; i++) {
    left_idx[A[i]] = min(left_idx[A[i]], i);
    right_idx[A[i]] = max(right_idx[A[i]], i);
  }
  memset(dp, -1, sizeof(dp));
  cout << memo(0) << endl;
  return 0;
}