ABC128-D: equeue

작성일

https://atcoder.jp/contests/abc128/tasks/abc128_d

  • 일단 K번 choice 할 수 있는데, 이때 가능한 연산이 4가지여서 얼핏보면 $4^{100}$ 개의 선택으로 보인다.
  • 고민을 잘 하다보면, 왼쪽과 오른쪽을 나눠서 생각할 수 있다는 것을 알게되고
  • 또 고민을 하다보면 A연산의 수와 B연산의 수가 정해지면 항상 optimal한 해를 정렬만 하면 찾을 수 있다는 것을 알 수 있다.
    • 정확히 말하면 A개를 뽑고, 그중에서 작은 순서대로 음수를 B개 집어넣는 것이다.
  • 여기까지 고민하고 풀었는데 $O(R^4 \log{R})$이 나온다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
 
int N, K;
vector<int> value;
 
int main() {
  cin >> N >> K;
  int maxV = 0;
  for(int i = 0; i < N; i++) {
    int v;
    cin >> v;
    value.push_back(v);
    if(v > 0) maxV += v;
  }
  if (K >= 2*N) {
    cout << maxV;
    return 0;
  }
  int ans = 0;
  for(int a = 0; a <= K; a++) {
    for(int b = 0; b <= K-a; b++) {
      for(int c = 0; c <= K-a-b; c++) {
        int d = K-a-b-c;
        priority_queue<int, vector<int>, std::greater<int>> left;
        int lsum = 0;
        for(int i = 0; i < a; i++)
          left.push(value[i]), lsum += value[i];
        for(int i = 0; i < b && left.size(); i++) {
          if(left.top() > 0) break;
          lsum -= left.top(); left.pop();
        }
 
        priority_queue<int, vector<int>, std::greater<int>> right;
        int rsum = 0;
        for(int i = 0; i < c; i++)
          right.push(value[value.size()-1-i]), rsum += value[value.size()-1-i];
        for(int i = 0; i < d && right.size(); i++) {
          if(right.top() > 0) break;
          rsum -= right.top(); right.pop();
        }
        ans = max(ans, lsum+rsum);
      }
    }
  }
  cout << ans;
}
  • 대회 끝나고 풀이를 보니, 몇단계 최적화가 더 있다. A와 B가 정해지면 C와 D는 신경쓸 것 없이 더 이득보는 것을 집어넣는 식으로 최적화 할 수 있다.
    • 이 경우는 $O(R^3 \log{R})$ 에 풀 수 있다. (복습하자)
  • Editorial에 보면 $O(R^2 \log{R})$ 인 해가 있다고 한다. B를 1만큼 shift 할 때 버려지는 연산이 2개 뿐이란 것을 이용하란다. 솔직히 풀이를 봐도 뭔말인지 모르긋다.