[Codeforces Round 981(Div.3)] - D. Kosuke's Assignment

https://codeforces.com/contest/2033/problem/D

Codeforces Round 981(Div.3) - D. Kosuke's Assignment

문제 유형: 부분합, 그리디, 다이나믹 프로그래밍

시간 제한: 2초

메모리 제한: 256MB

 

문제

After a trip with Sakurako, Kousuke was very scared because he forgot about his programming assignment.

In this assignment, the teacher gave him an array a of n integers and asked him to calculate the number of non-overlapping segments of the array a, such that each segment is considered beautiful.

A segment [l,r] is considered beautiful if al+al+1+⋯+ar−1+ar=0.

For a fixed array a, your task is to compute the maximum number of non-overlapping beautiful segments.

 

Sakurako와 여행을 다녀온 Kosuke는 프로그래밍 과제를 잊어버렸다는 사실에 무척 놀랐습니다. 이 과제에서 선생님은 그에게  n 개의 정수로 이루어진 배열  a 를 주고, 이 배열에서 비겹치는 구간(segment)의 개수를 구하라고 했습니다. 각 구간은 “아름다운 구간”으로 간주되어야 합니다.

구간 [l, r]이 “아름답다”고 여겨지려면, 해당 구간의 모든 원소 합 \( a_l + a_{l+1} + \dots + a_{r-1} + a_r = 0 \)이어야 합니다.

주어진 배열  a 에 대해, 비겹치는 “아름다운 구간”의 최대 개수를 계산하는 것이 목표입니다.

 

입력

The first line of input contains the number t (1≤t≤104) — the number of test cases. Each test case consists of 2

lines.

• The first line contains one integer n (1≤n≤10^5) — the length of the array.

• The second line contains n integers ai (−10^5≤ai≤10^5) — the elements of the array a.

 

It is guaranteed that the sum of n across all test cases does not exceed 3⋅10^5.

 

첫 번째 줄에는 테스트 케이스의 수  t 가 주어집니다. (1 <= t <= 10^4)

각 테스트 케이스는 2줄로 구성됩니다.

1. 첫 번째 줄에는 하나의 정수  n 이 주어집니다. (1 <= n <= 10^5)

2. 두 번째 줄에는  n 개의 정수  a_i  (-10^5 <= a_i <= 10^5)가 주어집니다.

 

 n 의 총 합은 모든 테스트 케이스를 합하여  3 x 10^5 을 넘지 않습니다.

 

출력

For each test case, output a single integer: the maximum number of non-overlapping beautiful segments.

각 테스트 케이스에 대해, 비겹치는 “아름다운 구간”의 최대 개수를 나타내는 정수를 한 줄에 출력합니다.

 

풀이

인덱스 0부터 현재까지의 부분합을 구해서, 이전에 존재한 적 있는 수이고, 그 수가 마지막으로 등장한 인덱스가 기존 아름다운 구간의 끝지점 이후라면, 아름다운 구간의 끝을 업데이트하고, 개수를 1 누적시킨다.

해시 충돌 공격을 막기 위해, 커스텀 해시 스니펫을 이용해주자.

 

dp를 이용할 수도 있지만, 여기서는 넘어간다.

 

코드

C++

#include <bits/stdc++.h>
#define ll long long
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;
  int ans = 0;

  ll sum = 0;
  int last = -2;
  unordered_map<ll, int, custom_hash> mp;
  mp[0] = -1;

  int temp;
  for (int i = 0; i < n; ++i) {
    cin >> temp;
    sum += temp;
    if (mp[sum] != 0 && mp[sum] >= last) {
      ans++;
      last = i + 1;
    }
    mp[sum] = i + 1;
  }
  cout << ans << "\n";
}

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