[Codeforces Round 1000(Div. 2)] D. Game With Triangles

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

Codeforces Round 1000(Div. 2) - D. Game With Triangles

문제 유형: 그리디, 수학, 기하학, 삼분 탐색, 구현, 투 포인터, 브루트 포스, 부분합, 구간합

시간 제한: 2초

메모리 제한: 256MB

 

문제

There are n+m distinct points (a1,0),(a2,0),…,(an,0),(b1,2),(b2,2),…,(bm,2) on the plane. Initially, your score is 0

. To increase your score, you can perform the following operation:

• Choose three distinct points which are not collinear;
• Increase your score by the area of the triangle formed by these three points;
• Then, erase the three points from the plane.

Let kmax be the maximum number of operations that can be performed. For example, if it is impossible to perform any operation, kmax is 0. Additionally, define f(k) as the maximum possible score achievable by performing the operation exactly k times. Here, f(k) is defined for all integers k such that 0≤k≤kmax.

Find the value of kmax, and find the values of f(x) for all integers x=1,2,…,kmax independently.

 

n + m개의 중복되지 않는 점들 (a1, 0), (a2, 0), ..., (an, 0), (b1, 2), (b2, 2), ..., (bm, 2)가 평면 위에 있다.

처음에는 0점부터 시작해서, 다음의 연산을 따른다:

• 세 개의 다른 점을 고른다. 세 점이 모두 한 직선위에 있으면 안된다.
• 세 개의 점으로 이루는 삼각형의 넓이만큼 점수를 더한다.
• 삼각형을 없앤다.

kmax를 최대 수행할 수 있는 횟수라고 하자.

0번 가능하면, kmax는 0인 것이다.

f(k)를 k번 연산시에 얻는 최대 점수라고 했을 때, kmax를 구하고 f(x)( for x = 1, 2, ..., kmax )를 구하시오.

 

입력

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤3⋅10^4).

The description of the test cases follows.

The first line of each test case contains two integers n and m (1≤n,m≤2⋅10^5).

The second line of each test case contains n pairwise distinct integers a1,a2,…,an — the points on y=0 (−10^9≤ai≤10^9).

The third line of each test case contains m pairwise distinct integers b1,b2,…,bm — the points on y=2 (−10^9≤bi≤10^9).

It is guaranteed that both the sum of n and the sum of m over all test cases do not exceed 2⋅10^5.

 

여러 테스트케이스가 있습니다. 첫 줄에 테스트케이스의 수 t가 주어집니다.

각 테스트케이스에서 첫 줄은 n과 m이 공백으로 구분되어 주어집니다.

테스트케이스의 두 번째 줄은 y=0인, 즉 a1, a2, ... an의 값이 있습니다.

테스트케이스의 세 번째 줄은 y=2인, 즉 b1, b2, ..., bn의 값이 있습니다.

 

출력

For each test case, given that the maximum number of operations is kmax, you must output at most two lines:

• The first line contains the value of kmax;

 

• The second line contains kmax integers denoting f(1),f(2),…,f(kmax). You are allowed to omit this line if kmax is 0.

 

Note that under the constraints of this problem, it can be shown that all values of f(x) are integers no greater than 10^16.

 

각 테스트케이스별로,

첫 줄에는 kmax의 값을,

두 번째 줄에는 k(1), k(2), ... k(kmax)의 값을 나열하시오.

 

풀이

Editorial: https://codeforces.com/blog/entry/138593

우선, 삼각형의 넓이는 같은 y를 가진 두 점끼리의 x축 차이라는 것을 알 수 있다.

y차이가 2이므로, 자명하다.

 

a에서 점을 두 개골라서 삼각형을 만드는 것을 오퍼레이션 A,

b에서 점을 두 개골라서 삼각형을 만드는 것을 오퍼레이션 B라고 하자.

오퍼레이션 A를 p번한다고 하고, 오퍼레이션 B를 q번한다고 하면, 수식g(p, q)은 다음과 같다.

\sum_{i=1}^{p}(A{_{n+1-i}}) + \sum_{i=1}^{q}(B{_{n+1-i}})

 

왜냐하면, 삼각형을 구성할 때, 그리디하게 양쪽 끝에 있는 것을 삭제하는 것이 이득이기 때문이다.

그리고, p와 q는 각각 x, k-x이다.

 

단, 횟수에 제약이 필요하다.

• 2p+q <= n
• p+2q <= m
• p >= 0
• q >= 0

이 조건들에 x와 k-x를 대입하고 정리하면..

• x <= n-k
• x >= m-2k
• x >= 0
• x <= k

가 된다.

즉, x는 max(0, 2k-m) <= x <= min(k, n-k)의 범위를 가진다.

 

이제, g(p, q)를 어떻게 빠르게 구할 수 있을까? p와 q를 어떻게 정해야 할까?

미리 구간합을 구해놓으면 된다. prefixSum이 좀 특이한데, 이전 prefix Sum에 배열값을 더하는게 아니라, 짝이 될 수와의 차를 누적하는 것이다.

그렇게 aSum과 bSum의 합은 볼록 함수(convex function)의 형태를 가져서, 처음부터 특정 구간동안은 증가하고, 그 이후에는 감소하는 형태이다.

그래서, 최대값을 빠르게 찾기 위해, 삼분 탐색을 이용한다.

만약 왼쪽이 더 크다면, 오른쪽의 범위를 줄인다.

만약 오른쪽이 더 크다면, 왼쪽의 범위를 줄인다.

이렇게 하면, 불필요한 계산 범위를 줄일 수 있다.

그 뒤 조정된 [l, r]의 범위에서 최대값을 구하면 된다.

 

이를 x가 유효한 범위를 갖는 동안 반복하여 배열에 담아두고, 적절히 출력해주면 된다.

 

코드

C++

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

ll f(int x, int ka, vector<ll> &aSum, vector<ll> &bSum) {
  return aSum[ka] + bSum[x - ka];
}

void solve() {
  int n, m;
  cin >> n >> m;
  vector<ll> a(n), b(m);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  for (int i = 0; i < m; ++i) {
    cin >> b[i];
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

  vector<ll> aSum(n + 1);
  vector<ll> bSum(m + 1);
  for (int i = 1; i <= n; ++i) {
    aSum[i] = aSum[i - 1] + a[n - i] - a[i - 1];
  }
  for (int i = 1; i <= m; ++i) {
    bSum[i] = bSum[i - 1] + b[m - i] - b[i - 1];
  }

  vector<ll> ans;

  for (int x = 1; 2 * x - m <= n - x; ++x) {
    ll l = max(0, 2 * x - m);
    ll r = min(x, n - x);

    if (l > r)
      break;

    while (r - l > 3) {
      ll ml = (l * 2 + r) / 3, mr = (l + r * 2) / 3;
      if (f(x, ml, aSum, bSum) > f(x, mr, aSum, bSum))
        r = mr;
      else
        l = ml;
    }

    ll mans = 0;
    for (int i = l; i <= r; ++i) {
      mans = max(mans, f(x, i, aSum, bSum));
    }
    ans.push_back(mans);
  }

  int kMax = ans.size();
  cout << kMax << "\n";
  for (const auto &elem : ans)
    cout << elem << " ";
  cout << "\n";
}

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