[Codeforces Round 1005(Div. 2)] B. Variety is Discouraged

https://codeforces.com/contest/2064/problem/B

Codeforces Round 1005(Div. 2) - B. Variety is Discouraged

문제 유형: 그리디, 해 구성하기, 슬라이딩 윈도우

시간 제한: 1.5초

메모리 제한: 256MB

 

문제

Define the score of an arbitrary array b to be the length of b minus the number of distinct elements in b

. For example:

• The score of [1,2,2,4] is 1, as it has length 4 and only 3 distinct elements (1, 2, 4).

• The score of [1,1,1] is 2, as it has length 3 and only 1 distinct element (1).

• The empty array has a score of 0.

 

You have an array a. You need to remove some non-empty contiguous subarray from a at most once.

More formally, you can do the following at most once:

• pick two integers l, r where 1≤l≤r≤n, and

• delete the contiguous subarray [al,…,ar] from a (that is, replace a with [a1,…,al−1,ar+1,…,an]).

 

Output an operation such that the score of a is maximum; if there are multiple answers, output one that minimises the final length of a after the operation. If there are still multiple answers, you may output any of them.

 

임의의 배열 b의 점수는 b의 길이에 b의 고유한 원소의 개수를 뺀 것이라고 하자.

배열 a가 주어진다.

아무것도 하지 않거나, [l, r]구간에 대해 삭제를 한 번 할 수 있다.

최고점수를 얻기 위한 l, r구간을삭제하는 위치를 출력하시오. 삭제하지 않을 경우 0을 리턴하시오.

만약 같은 점수라면, 더 짧은 배열이 남도록 하게 하시오.

 

입력

The first line contains an integer t (1≤t≤10^4) — the number of testcases.

The first line of each testcase contains an integer n (1≤n≤2⋅10^5) — the length of the array a.

The second line of each testcase contains n integers a1,a2,…,an (1≤ai≤n).

The sum of n across all testcases does not exceed 2⋅10^5.

 

첫째 줄에 테스트 케이스의 수 t가 주어집니다.

테스크 케이스의 첫째 줄은 정수 n을 가집니다. 배열 a의 길이입니다.

둘째 줄에는 배열의 요소 a1, a2, ..., an이 있습니다.

 

출력

For each testcase, if you wish to not make a move, output 0.

Otherwise, output two integers l and r (1≤l≤r≤n), representing the left and right bound of the removed subarray.

The removed subarray should be chosen such that the score is maximized, and over all such answers choose any of them that minimises the final length of the array.

 

아무 연산도 하지 않으면 0을 출력하시오.

아니라면, 구간, l, r을 출력하시오.

같은 점수라면, 남은 배열의 길이가 더 짧아지도록 하시오.

 

풀이

연산을 어떻게 잘 취하던, 점수가 더 늘어나지는 않는다.

즉, 최대값을 얻으려면 l, r구간은 a에서 unique한 요소들만을 담고 있어야 한다. 그래야 전체 길이도 줄고, unique한 요소수도 줄어서 유지를 하도록 하게 한다.

a에 있는 unique한 요소들만 들어있는 subarray의 가장 큰 범위를 구하면 된다.

만약 한 번이라도 못구했다면, 0을 출력하고 아니면 범위를 출력해주면 된다.

 

 

코드

C++

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

struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }

  template <typename T> size_t operator()(const T &x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(hash<T>{}(x) + FIXED_RANDOM);
  }

  template <typename T1, typename T2>
  size_t operator()(const pair<T1, T2> &p) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(operator()(p.first) ^ operator()(p.second) +
                                                FIXED_RANDOM);
  }

  template <typename... Args> size_t operator()(const tuple<Args...> &t) const {
    return apply(
        [this](const Args &...args) { return (operator()(args) ^ ...); }, t);
  }

  template <typename T> size_t operator()(const vector<T> &vec) const {
    size_t hash_value = 0;
    for (const T &elem : vec) {
      hash_value ^= operator()(elem) + 0x9e3779b9 + (hash_value << 6) +
                    (hash_value >> 2);
    }
    return hash_value;
  }
};

void solve() {
  int n;
  cin >> n;
  vector<int> a(n + 1);
  unordered_map<int, int, custom_hash> freq;

  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    freq[a[i]]++;
  }

  // 1개따리 서브어레이를 늘려라
  int ansL = 0, ansR = 0;
  int right = 1;
  for (int left = 1; left <= n; ++left) {
    if (freq[a[left]] != 1)
      continue;

    right = left;
    while (right <= n && freq[a[right]] == 1) {
      right++;
    }
    right--;

    if (ansR - ansL <= right - left) {
      ansR = right;
      ansL = left;
    }
    left = right;
  }

  if (n == 1) {
    ansL = 1;
    ansR = 1;
  }

  if (ansL == ansR && ansL == 0) {
    cout << "0\n";
  } else {
    cout << ansL << " " << ansR << "\n";
  }
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}