백준 20370 - 공정한 게임

https://www.acmicpc.net/problem/20370

발상과 사전 작업

문제의 상황과는 반대로 BOT_10에게 이득인 값들을 먼저 배정한다.

 

그다음부터 BOT_6584가 BOT_10이 가진 값을 일부 강탈하면서 요구하는 답을 최대화시킬 것이다.

 

따라서 BOT_10에게 큰 값을 주도록 B의 내림차순으로 주어진 수열을 정렬하도록 한다. A는 정렬 기준을 신경 쓰지 않아도 된다.

무엇을 강탈할까?

BOT_10이 가진 값을 강탈하기로 했는데 무엇을 강탈할지 잘 모르겠다.

 

문제를 다시 보면 [(자신이 고른 캐릭터들의 숙련도 합 - 상대방이 고른 캐릭터들의 숙련도 합)]을 최대화해야 하므로 BOT_6584의 기준으로 BOT_6584의 숙련도 합 - BOT_10의 숙련도 합이 된다.

 

우리는 다음과 같은 강탈 우선순위를 세울 것이다.

 

Ai + Bi가 큰 값을 높은 우선순위로 배정한다.

Ai + Bi요?

뜬금없이 두 개를 더한 값이 웬 말이냐?라는 의문이 있을 수 있다. 하지만 앞의 내용을 찬찬히 생각하면 금방 납득할 수 있다.

 

우리는 앞서 BOT_10에게 미리 값을 배정한다고 했다. 그런데 인덱스 i를 강탈하면? 그렇다. BOT_10은 자기의 힘 Bi를 잃으면서도 상대에게 Ai만큼의 힘을 주게 되는 것이다.

 

즉 BOT_6584의 입장에서는 자기가 높은 숙련도를 얻든, BOT_10의 숙련도를 무지막지하게 떨어트리든 하면 되므로 Ai + Bi가 큰 값을 우선순위를 기준으로 삼는 것이다.

 

하여튼 이런 방식으로 강탈 방법을 세울 수 있다.

이게 다가 아니다

그렇다. 가장 중요한 이것도 고려해야 한다.

 

단순히 Ai가 큰 값

 

제일 자명한 부분이다. 어쨌든 Ai가 큰 값을 먹는 것도 중요하다. BOT_10한테 값을 1개 강탈한다고 하면 나머지 K - 1개의 값은 Ai가 큰 순서대로 먹어야 함은 너무나도 잘 알 수 있다.

비중을 정하기

그래. 값을 강탈하고 Ai가 큰 값을 가져가야 하는 건 알겠다. 몇 개 강탈할지 어떻게 정하지?

 

그냥 단순하게 x(0 <= x <= k)개 강탈하고 k - x개 높은 Ai를 가져갔을 때 최댓값을 구하면 된다.

구현

대충 글로는 이해했다. 이제 구현할 시간이다... 어떻게 구현하지?

 

먼저 이 문제의 풀이를 위해선 누적합, 우선순위 큐, 그리고 우선순위 큐에 의한 누적합이 필요하다.

 

다음 누적합들을 정의한다.

 

pref_bot10 := BOT_10이 값들을 가져갔을 때 얻는 숙련도의 합을 누적합으로 나타낸 것이다. 위에서 이미 Bi의 내림차순으로 정렬했으므로 임의의 구간에서 BOT_10이 최선의 선택을 했음이 자동으로 증명된다.

 

우리는 구한 BOT_6584의 숙련도 합에서 pref_bot10을 빼는 방식으로 (BOT_6584가 고른 캐릭터들의 숙련도 합 - BOT_10이 고른 캐릭터들의 숙련도 합)을 구할 것이다.

 

suf_bot6584 := BOT_6584가 값들을 가져갔을 때 얻는 숙련도의 합을 누적합으로 나타낸 것이다. suf에서 짐작할 수 있듯이 배열의 뒤부터 suffix 누적합을 계산한다. 왜 suffiix냐면 prefix에서는 값을 강탈할 거기 때문에 suffix에서 Ai를 가져가는 경우를 고려한다.

 

이때 배열은 Ai 기준으로 정렬된 상태가 아니므로 우선순위 큐로 다시 정렬하여 큰 값을 불러오도록 한다.

 

revoke_bot10 := BOT_10한테 값을 강탈하면서 BOT_6584가 얻는 이득의 누적합이다. 역시 이때도 배열은 Ai + Bi를 기준으로 정렬되지 않았으므로 우선순위 큐로 다시 한번 정리할 필요가 있다.

 

그러면 대략적인 식은 다음과 같이 산출된다.

 

answer = -pref_bot10 + suf_bot6584 + revoke_bot10

 

반복문을 돌면서 각 누적합으로 계산된 값 중 최댓값을 찾아주도록 한다.

 

참고로 BOT_10은 최소 k개의 값을 점거해야 하고(6584에게 일부 값을 뺏기고도 k개의 값을 취득해야 한다.)

 

아무리 많이 뺏겨도 K개 뺏기므로(2K개 점거했을 때 K개 뺏기면 K개 남음) 허용하는 인덱스 범위는 0-based 기준 K - 1부터 2K - 1까지다.

 

이를 잘 유의해서 구현하면 된다. 구현에 대해 잘 모르겠으면 아래 코드를 참조하도록 한다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int n, k;
pii ar[80000];
ll pref_bot10[80000];
ll revoke_bot10[80001];
ll suf_bot6584[80001];
priority_queue<ll> pq1, pq2;
 
void solve()
{
  cin >> n >> k;
  for (int i = 0; i < n; i++)
  {
    cin >> ar[i].first;
  }
  for (int i = 0; i < n; i++)
  {
    cin >> ar[i].second;
  }
 
  sort(ar, ar + n, [](pii &l, pii &r) {
    return l.second > r.second or (l.second == r.second and l.first > r.first);
  });
 
  ll ans = -1e18;
 
  pref_bot10[0] = ar[0].second;
  for (int i = 1; i < n; i++)
  {
    pref_bot10[i] = pref_bot10[i - 1] + ar[i].second;
  }
 
  for (int i = 0; i < n; i++)
  {
    pq1.push(ar[i].first + ar[i].second);
 
    if (i < k) continue;
 
    revoke_bot10[i] = revoke_bot10[i - 1] + pq1.top();
    pq1.pop();
  }
 
  for (int i = n - 1; i >= 0; i--)
  {
    pq2.push(ar[i].first);
 
    if (i >= k + k) continue;
 
    suf_bot6584[i] = suf_bot6584[i + 1] + pq2.top();
    pq2.pop();
  }
 
  for (int i = k - 1; i < k + k; i++)
  {
    ans = max(ans, revoke_bot10[i] - pref_bot10[i] + suf_bot6584[i + 1]);
  }
 
  cout << ans;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록