과거 청산 챌린지 #4

슬슬 문제를 푸는 것이 귀찮아지고 있다. D4-D3권에서 남은 문제들을 푸는 것이 쉽지 않아 보인다. 그래도 아직 문제가 꽤 남았으니 이 부분에서 조금 더 풀어 볼 생각이다.

 

뭔가 문제를 푼 사람이 많을수록 더 풀기 쉬울 것 같으니, 이번에는 푼 사람 순서대로 정렬을 해 봤다.

 

남은 문제: 60 → 55문제

BOJ 20558. 쿼리와 수열

$K_i$의 합을 $K$라고 쓰자. 다음과 같이 상태가 $O(NK)$개인 DP를 만드는 것은 쉽다.

• $DP[i][j][v]$: 구간 $(i, j)$에서 최댓값이 $v$인 경우 답의 최댓값
  이때 $(i, v)$ 또는 $(j, v)$의 쌍이 $K$개 이하이므로 전체 $(i, j, k)$의 쌍이 $O(NK)$개 이하가 된다. 다만 저렇게 하면 transition의 가짓수가 $K$개까지 될 수 있어서 실제 시간 복잡도는 $O(NK^2)$이 된다.

여기까지 생각해 놓고 한동안 진전이 없어서 에디토리얼을 봤다. 에디토리얼이 굉장히 대충 써 있어서, 이해하는 데 시간이 많이 걸렸다.

 

에디토리얼을 조금 더 자세히 살펴보며 어떤 방향의 풀이인지 정리해 보자.

 

$DP[l][r]$을 구간 $[l, r]$만 고려했을 때의 답이라고 정의하자. 여기서 구간 $[l, r]$만 고려했을 때의 답은, $[l, r]$에 포함되는 구간의 최댓값 쿼리 합에서 $[l, r]$ 구간을 만드는 비용을 뺀 것을 말한다.

 

에디토리얼의 첫 번째 장에 의하면 $DP[l][r] = \max_{l \le k \le r}{(DP[l][k-1] + DP[k+1][r] + cost(l, r, k))}$라고 한다. 이때 $cost(l, r, k)$는 구간 $(l, r)$에서 $A_k$를 최댓값이라 가정했을 때, $k$를 포함하는 구간에 해당하는 최댓값 합에서 $A_k$를 지정하는 비용을 뺀 값 중 가능한 최댓값이라고 생각할 수 있다.

 

정의를 보고 나면, $A_l, \cdots, A_r$이 주어졌을 때 그 중 최대인 $k \in [l, r]$이 반드시 존재하기 때문에, 저러한 $k$를 고르고 나면 $DP[l][r]$이 반드시 그 값과 일치하는 게 가능함을 알 수 있다. 따라서 (좌변) >= (우변)이 성립한다. 또한, 최댓값이 반드시 성립하므로, 그때의 $k$를 골랐을 때 (좌변) > (우변)이면 그것도 그것대로 문제임을 알 수 있다. 우변의 일부 항이 최적이 아니라는 뜻이기 때문이다. 따라서 저렇게 정의하고 나면 (좌변) = (우변)이 성립해야 한다.

 

다만 이렇게 읽고 나면 한 가지 의문이 들 수 있다. 지금 이 DP는 최댓값이 무엇인지에 대한 데이터를 전혀 포함하지 않고 있기 때문이다. 예를 들어, $DP[l][r]$은 $A_k$가 최대임을 가정하는데, $DP[l][k-1]$에서 고른 최댓값이 $A_k$보다 더 큰 경우 모순이 생긴다. 이런 경우 어떻게 처리되는가? 사실 이 풀이의 핵심은 이렇게 DP 전이 과정에서 최댓값을 잘못 고를 경우 오히려 손해를 본다는 데에서 온다. 최댓값을 잘못 골랐다고 생각해 보자. 그렇다면 일부 구간 $[s, e] \subset [l, r]$에 대해, $[s, e]$ 구간의 최댓값이 저평가된 구간들이 생기게 된다. 이런 경우, 실제로 얻을 수 있는 답의 최댓값보다 최댓값 합 부분에서 손해를 보게 되므로, 그냥 DP를 진행해도 문제가 없다는 것이다. 어차피 최적의 답은 구해질 것이고, 조건에 맞지 않는 답들이 구해져도 최적의 답보다 작기 때문에 영향을 주지 않는다.

 

여기까지 왔으면 저 DP를 어떻게 처리하는가가 핵심이 된다. 요점은 $[l, r]$ 구간에서 적당한 $A_k = v$를 골라, $[l, r]$ 구간에서 $k$를 포함하는 쿼리가 $Q_{l, r, k}$개라 할 때, $Q_{l, r, k} v_{k, j} - C_{k, j}$의 최댓값을 모든 빠르게 구할 수 있어야 한다. $(l, r)$이 주어지면 저런 $(k, v)$ 쌍 개수가 총 $K$개라서, 나이브하게 하면 $O(n^2 K)$가 되어 너무 느리다.

 

핵심은 저 상황을 직선 형태 (CHT 꼴)로 보는 것이다. 결국 한 $k$에 대해서 저걸 전부 모아보면 $ax-b$ 꼴로 쓸 수 있는데, $Q_{l, r, k} = x$에 무엇이 들어오냐에 따라서 최적인 직선이 바뀔 것이다. 이렇게 하면 $K$를 $n$으로 바꿔 대략 $O(n^3)$ 또는 $O(n^3 \log n)$ 정도의 시간 복잡도에 풀 수 있게 된다.

 

CHT를 오랜만에 짜서, while문 조건을 잘못 쓰는 바람에 오랫동안 맞왜틀했다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
ll S[302][302];
ll cost[302][302][302];
ll DP[302][302];

inline ll ssum(int l, int r, int k){
    return S[k][k] - S[l-1][k] - S[k][r+1] + S[l-1][r+1];
}

inline ll divCeil(ll a, ll b){
    if(a >= 0) return (a+b-1)/b;
    else return -((-a)/b);
}

struct Line{
    ll a, b, st;
    Line(ll a, ll b): a(a), b(b){}
    Line(ll a, ll b, ll st): a(a), b(b), st(st){}

    inline ll get(ll x){
        return a*x+b;
    }

    friend ll intersect(Line &l1, Line &l2){ // l1이 더 기울기가 작음. l1 < l2가 되는 최소 정수 x좌표
        assert(l1.a < l2.a);
        return divCeil(l1.b - l2.b, l2.a - l1.a);
    }

    bool operator<(const Line &r)const{
        return st < r.st;
    }
};
vector<Line> lines[302];

int main(){
    #ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    #endif

    cin >> n;
    for(int i=1; i<=n; i++) for(int j=i; j<=n; j++) cin >> S[i][j];
    for(int i=1; i<=n; i++) for(int j=n; j>=i; j--){
        S[i][j] += S[i-1][j] + S[i][j+1] - S[i-1][j+1];
    }

    for(int i=1; i<=n; i++){
        int k;
        cin >> k;
        vector<pair<ll, ll> > vec (k);
        for(int i=0; i<k; i++){
            cin >> vec[i].first >> vec[i].second;
            vec[i].second *= -1;
        }

        sort(vec.begin(), vec.end());

        for(auto [a, b]: vec){
            Line line (a, b);
            while(lines[i].size() >= 2 &&
                  intersect(lines[i][lines[i].size()-2], lines[i].back()) >= intersect(lines[i].back(), line)){
                lines[i].pop_back();
            }
            line.st = lines[i].empty() ? LLONG_MIN : intersect(lines[i].back(), line);
            lines[i].push_back(line);
        }
    }

    for(int l=1; l<=n; l++) for(int r=l; r<=n; r++){
        for(int m=l; m<=r; m++){
            ll s = ssum(l, r, m);
            auto it = upper_bound(lines[m].begin(), lines[m].end(), Line(0, 0, s)) - 1;
            cost[l][r][m] = it->get(s);
        }
    }

    for(int i=1; i<=n; i++) DP[i][i] = cost[i][i][i];
    for(int d=1; d<n; d++){
        for(int l=1; l+d<=n; l++){
            int r = l+d;
            DP[l][r] = LLONG_MIN;
            for(int m=l; m<=r; m++){
                DP[l][r] = max(DP[l][r], (l==m ? 0 : DP[l][m-1]) + (r==m ? 0 : DP[m+1][r]) + cost[l][r][m]);
            }
            assert(DP[l][r] != LLONG_MIN);
        }
    }
    cout << DP[1][n];
}

BOJ 31951. Comparator

일단 파싱을 잘 해야 한다. 스택에서 연산자 우선순위로 잘 비교하고 enum 등을 사용하면 구현을 최대한 간단히 할 수 있다.

 

다음으로 파싱 결과에서 $2^k \times 2^k$ 크기의 비교 테이블을 얻어야 한다. 그런데 유의미한 조건은 사실 최대 $4k^2$개뿐이라는 사실을 알 수 있다. 각 $(x, y, xv, yv)$별로 한 번씩만 해도 충분하기 때문이다. 저런 tuple이 총 $4k^2$개 있고, 각 tuple에 대해 유효한 수 쌍이 $(2^{k-1})^2$개 있으니, 이 경우들에 대해서만 나이브하게 돌아봐도 충분히 빠르게 table을 만들 수 있다.

 

table을 만들고 나면 세 가지 속성을 세어야 한다. 앞 두 개는 자명하고, 나머지 하나도 bitset을 쓰면 빠르게 셀 수 있다.

 

결과적으로 $O(n+2^{3k}/w)$ 시간에 문제를 해결할 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void input();
void makeTable();
void solve();

int main(){
    #ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    #endif

    input();
    makeTable();
    solve();
}

int n, k;
int A[200002], B[200002], S[200002], R[200002];

enum Op {
    ZERO = 0, ONE = 1,
    LP = 2, RP = 3,
    XOR = 4, OR = 5, AND = 6, EQ = 7, NOT = 8
};

inline int opc(Op l, Op m, Op r){
    assert((l == ZERO || l == ONE) && (r == ZERO || r == ONE));
    if(m == XOR) return l ^ r;
    if(m == OR) return l | r;
    if(m == AND) return l & r;
    if(m == EQ) return l == r;
    if(m == NOT) return !r;
    exit(1);
}

int real_evaluate(string expr){
    expr = '(' + expr + ')';

    vector<Op> stk;
    for(char c: expr){
        if(c == '0') stk.push_back(ZERO);
        else if(c == '1') stk.push_back(ONE);
        else if(c == '(') stk.push_back(LP);
        else if(c == ')'){
            while(stk[stk.size() - 2] != LP){
                Op r = stk.back(); stk.pop_back();
                Op m = stk.back(); stk.pop_back();
                Op l = stk.back(); stk.pop_back();
                stk.push_back((Op)opc(l, m, r));
            }
            Op save = stk.back();
            stk.pop_back(); stk.pop_back();
            stk.push_back(save);
        }
        else{
            Op cur = (c == '^' ? XOR : c == '|' ? OR : c == '&' ? AND : c == '=' ? EQ : NOT);
            if(cur == NOT) stk.push_back(ZERO); // 단항 연산자 처리

            while((int)stk.size() >= 3 && stk[stk.size()-2] > cur){
                Op r = stk.back(); stk.pop_back();
                Op m = stk.back(); stk.pop_back();
                Op l = stk.back(); stk.pop_back();
                stk.push_back((Op)opc(l, m, r));
            }
            stk.push_back(cur);
        }
    }

    assert((int)stk.size() == 1 && (stk[0] == ZERO || stk[0] == ONE));
    return stk[0] == ONE ? 1 : 0;
}

int evaluate(string expr){
    int ret = 0;
    for(int a=0; a<2; a++){
        for(int b=0; b<2; b++){
            string newExpr = expr;
            for(auto &c: newExpr){
                if(c == 'x') c = '0' + a;
                if(c == 'y') c = '0' + b;
            }
            int val = real_evaluate(newExpr);
            ret += val << (a*2+b);
        }
    }
    return ret;
}

void input(){
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        int a, b, r;
        string expr;
        cin >> a >> b >> expr >> r;
        int bs = evaluate(expr);
        A[i] = a-1, B[i] = b-1, S[i] = bs, R[i] = r;
        // cout << S[i] << '\n';
    }
}

int table[1<<10][1<<10]; // 0, 1: 결과, 2: 결정 x
int did[10][10][2][2];
int numbers[10][2][1<<9];

void makeTable(){
    int MX = (1<<k);
    for(int i=0; i<MX; i++) for(int j=0; j<MX; j++) table[i][j] = 2;

    for(int i=0; i<k; i++) for(int j=0; j<2; j++){
        int cnt = 0;
        for(int s=0; s<MX; s++){
            int b = (s>>i) & 1;
            if(b == j) numbers[i][j][cnt++] = s;
        }
    }

    for(int i=1; i<=n; i++){
        int a = A[i], b = B[i], s = S[i], r = R[i];
        for(int x=0; x<2; x++) for(int y=0; y<2; y++){
            if((s & (1<<(x*2+y))) == 0 || did[a][b][x][y]) continue;
            did[a][b][x][y] = 1;
            for(int ia=0; ia<(1<<(k-1)); ia++){
                int na = numbers[a][x][ia];
                for(int ib=0; ib<(1<<(k-1)); ib++){
                    int nb = numbers[b][y][ib];
                    if(table[na][nb] == 2) table[na][nb] = r;
                }
            }
        }
    }
    int ret;
    cin >> ret;

    for(int i=0; i<MX; i++) for(int j=0; j<MX; j++) if(table[i][j] == 2) table[i][j] = ret;
}

bitset<1024> out[1<<10], in[1<<10];

void solve(){
    const int MX = (1<<k);
    { // reflexive
        int cnt = 0;
        for(int i=0; i<MX; i++) if(table[i][i]) cnt++;
        cout << cnt << ' ';
    }
    { // symmetric
        int cnt = 0;
        for(int i=0; i<MX; i++) for(int j=0; j<MX; j++){
            if(table[i][j] && table[j][i]) cnt++;
        }
        cout << cnt << ' ';
    }
    { // transitive
        for(int i=0; i<MX; i++) for(int j=0; j<MX; j++){
            if(table[i][j]){
                out[i][j] = 1;
                in[j][i] = 1;
            }
        }

        ll ans = 0;
        for(int i=0; i<MX; i++) for(int k=0; k<MX; k++){
            if(table[i][k]) continue;
            ans += (out[i] & in[k]).count();
        }
        cout << ans;
    }
}

BOJ 17376. 룰렛

문제 자체를 봤을 때는 수식 전개하기가 조금 힘들 것 같았고, 구현도 조금 복잡할 것 같았다.

일단 문제의 상황을 몇 가지 적당한 확률로 나타내는 것이 중요하다. 아래와 같이 정의해 보자.

• $S[x]$: 놀이기구 $x$에서 출발했을 때, 마지막으로 놀이기구 $x$를 타고 집으로 돌아갈 확률
• $T[e]$: 간선 $e = x \rightarrow y$에 대해, 놀이기구 $x$에서 출발했을 때, 한 번이라도 간선 $e$를 탈 확률
• $C[e]$: 간선 $e = x \rightarrow y$에 대해, 놀이기구 $x$에서 출발했을 때, 도착점이 간선 $e$ 기준으로 $y$ 쪽 서브트리에 있을 확률

이제 이 확률 사이의 관계를 나타내어 보자. 다음을 알 수 있다. 여기서 $Pr[e]$는 $e = (x, y)$일 때 $x$에서 바로 간선 $e$를 탈 확률, $Pr[v]$는 $v$에 있을 때 해당 지점에서 바로 멈출 확률, $e'$는 $e$의 역방향 간선이라고 정의한다.

 

$$
\begin{aligned}
S[x] &= 1 - \sum_{e = (x, y) \in E} C[e] \\
S[x] &= Pr[x] + \left(\sum_{e = (x, y) \in E} Pr[e] T[e'] \right) S[x] \\
&= \frac{Pr[x]}{1 - \sum_e Pr[e] T[e']} \\
C[e] &= T[e] (1 - T[e']) + T[e]T[e']T[e](1-T[e'])+ \cdots \\
&= \frac{T[e](1-T[e'])}{1 - T[e]T[e']}
\end{aligned}
$$

 

이렇게 식을 쓰다 보면 결국 $T[e]$를 모두 구해 두는 것이 굉장히 중요함을 알 수 있다. $T[e]$를 $T$에 대해 나타내 보면

 

$$
\begin{aligned}
T[e] &= Pr[e] + \left( \sum_{f = (x, y) \neq e} Pr[f] T[f'] \right) T[e] \\
&= \frac{Pr[e]}{1 - \sum_{f \neq e} Pr[f] T[f']}
\end{aligned}
$$

그런데 여기서 잘 생각해보면 저 $T[e]$ 값은 rerooting DP가 되는 꼴로 나온다. 따라서 저 $T[e]$를 사전에 모두 구해둘 수 있다. 이제 $T$로부터 $C$를 만들고, $C$로부터 $S$를 만들어 두면 각 쿼리는 단순히 트리 위의 구간 쿼리 처리가 된다. $O(N + Q \log N)$에 문제를 해결할 수 있다.

#include <bits/stdc++.h>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;

typedef modint1000000007 ll;

istream& operator>>(istream &in, ll &m){
    long long x;
    in >> x;
    m = ll(x);
    return in;
}

int n, q;
ll A[100002]; int par[100002];
int depth[100002];
vector<pair<int, ll> > edge[100002];

ll Prup[100002], Prdown[100002];
ll Tup[100002];

void dfsT(int x, int p=-1){
    if(p!=-1){
        par[x] = p;
        auto it = edge[x].begin();
        while(it->first != p) ++it;
        Prup[x] = it->second / A[x];
        edge[x].erase(it);
    }

    ll a = Prup[x], b = 1;

    for(auto [y, p1]: edge[x]){
        Prdown[y] = p1 / A[x];
        depth[y] = depth[x] + 1;
        dfsT(y, x);
        b -= Prdown[y] * Tup[y];
    }
    Tup[x] = a / b;
}

ll Tdown[100002];

void dfsT2(int x, int p=-1){
    ll sum = 0;
    for(auto [y, p1]: edge[x]) sum += Prdown[y] * Tup[y];
    if(p != -1) sum += Prup[x] * Tdown[x];
    for(auto [y, p1]: edge[x]){
        Tdown[y] = Prdown[y] / (1 - sum + Prdown[y] * Tup[y]);
        dfsT2(y, x);
    }
}

ll Cup[100002], Cdown[100002], S[100002];
int LCADB[100002][20];

ll TupS[100002], TdownS[100002];

void dfsSum(int x){
    for(auto [y, p1]: edge[x]){
        TupS[y] = TupS[x] * Tup[y];
        TdownS[y] = TdownS[x] * Tdown[y];
        dfsSum(y);
    }
}

int getLCA(int x, int y){
    if(depth[x] > depth[y]) swap(x, y);
    for(int d=0; d<20; d++) if((depth[y] - depth[x]) & (1<<d)) y = LCADB[y][d];
    if(x==y) return x;
    for(int d=19; d>=0; d--) if(LCADB[x][d] != LCADB[y][d]) x = LCADB[x][d], y = LCADB[y][d];
    return par[x];
}

int kthParent(int x, int k){
    for(int i=0; i<20; i++) if((k>>i)&1) x = LCADB[x][i];
    return x;
}

int main(){
    #ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    #endif

    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> A[i];

    for(int i=1; i<n; i++){
        int u, v; ll p1, p2;
        cin >> u >> v >> p1 >> p2;
        edge[u].push_back({v, p1});
        edge[v].push_back({u, p2});
    }

    dfsT(1);
    dfsT2(1);

    for(int i=2; i<=n; i++){
        ll tup = Tup[i], tdown = Tdown[i];
        Cup[i] = tup * (1 - tdown) / (1 - tup * tdown);
        Cdown[i] = tdown * (1 - tup) / (1 - tup * tdown);
    }
    for(int i=1; i<=n; i++){
        S[i] = 1;
        for(auto [y, p1]: edge[i]) S[i] -= Cdown[y];
        if(i != 1) S[i] -= Cup[i];
    }

    // debug
    #ifdef LOCAL
    for(int i=1; i<=n; i++){
        cout << i << ": " << S[i].val() << " " << Tup[i].val() << " " << Tdown[i].val() <<
                " " << Cup[i].val() << " " << Cdown[i].val() << "\n";
    }
    #endif

    for(int i=1; i<=n; i++) LCADB[i][0] = par[i];
    for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];

    TupS[1] = TdownS[1] = 1;
    dfsSum(1);

    while(q--){
        int x, y;
        cin >> x >> y;
        int z = getLCA(x, y);

        ll ans;
        if(x == y) ans = S[x];
        else{
            ans = TupS[x] / TupS[z] * TdownS[y] / TdownS[z];
            ans *= S[y];
        }
        cout << ans.val() << '\n';
    }
}

BOJ 10935. BASE64 인코딩

원래는 번외 문제는 다이아 이후로 미뤄 두려고 했는데, 영 의지가 없어서 쉬워 보이는 하나만 풀었다.

import base64
s = input()
b = s.encode('UTF-8')
print(base64.b64encode(b).decode('ascii'))

 

여기서부터 남은 다4/다3 문제들이 너무 답이 없어 보였다. 대부분 감이 잘 안 잡히거나, 어떻게 하는지는 알겠는데 TL/ML 상수 이슈로 풀기 싫은 것들이 너무 많았다. 그래서 여기서부터는 일단 조금 생각해보고 모르겠으면 풀이를 일찍 찾아보기로 했다.

BOJ 23851. Akcija

문제를 간단히 요약하면 다음과 같다.

 

$n$개의 상품이 있고, 각 상품은 가격 $w_i$와 데드라인 $d_i$가 있다. 1분에 최대 한 개의 상품을 살 수 있다. 즉, 어떤 상품 집합 $S$를 살 수 있을 조건은 (홀의 정리에 의해) 모든 $t$에 대해 $d_i \le t$인 상품이 $t$개 이하 있는 것이다. 모든 살 수 있는 집합을 크기 내림차순으로, 크기가 같다면 가격 합 오름차순으로 정렬할 때, $1$번째부터 $k$번째 집합의 크기와 가격 합을 구하면 된다.

Subtask 2

$k = 1$인 경우 최적의 해를 구하면 된다. 일단 개수를 구하는 것은 쉽다. 그냥 비용 무시하고 그리디하게 데드라인 작은 것부터 고르면 된다. 그런데 전체 비용을 구하는 것은 조금 더 어렵다. 여기서도 그리디한 전략을 쓸 수 있다. 최대 개수가 $s$라고 할 때, 처음에는 데드라인이 $s$ 이상인 것 중 최대를 고르고, 다음으로 데드라인이 $s-1$ 이상인 남은 것 중 최대를 고르고, ..., 이런 식으로 반복하면 된다.

Subtask 3

위와 같이 $k = 1$인 solution을 찾았으면, $k=2$인 solution은 이들 중 한 개를 제거하고 만들 수 있는 최적의 solution이 된다. 이들 중 가장 좋은 것을 찾으면 된다.

Subtask 4

$O(2^n)$에 다 해 보면 된다.

Subtask 5

Subtask 3의 접근을 생각해 보면, 일단 최적해를 구한 뒤, 하나를 다른 걸로 대체하는 식으로 다른 후보들을 만들어 나갈 수 있다고 생각할 수 있다. 이걸 적당히 효율적으로 짜면 Subtask 5를 풀 수 있을 것이다.

Full task

저걸 조금 최적화하면 Full task도 어렵지 않게 풀 수 있을 것 같긴 했는데, 옛날에 MLE를 받은 기록이 있어 (지금까지도 여러 번 겪은) TL/ML 상수 이슈에 휘말릴 것 같았다. 정해를 읽고 짜는 쪽이 더 깔끔할 것 같아 그렇게 하기로 했다.

그런데 에디토리얼도 내가 생각한 것 이상의 특별한 정보를 제공해주지 않았다. 결국 Robotic Cow Herd 느낌의 pq질을 해야 한다는 건 자명한데, 거기서 메모리를 어떻게 깎는지가 문제의 핵심 같아 보였다.

 

핵심은 현재 상태를 pq에 그대로 저장하지 말고, 이전 상태에서 어디가 바뀌는지만 저장하는 것이다. 이렇게 하면 $O(nk)$ 메모리로 문제를 해결할 수 있다.

 

디테일적인 면에서 생각할 게 꽤나 많은 문제인 것 같다. 자세한 디테일은 생략한다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Product{
    int d; ll v;
    Product(){}
    Product(int d, ll v): d(d), v(v){}
};

int n, k;
Product arr[2002];
bool used[2002][2002];
int sz[2002]; ll cost[2002];
unordered_set<ll> usedSets;
ll RAND[2002];

struct Solution{
    int sz; ll cost;
    int base, del, add; // until: 옮길 수 없는 가장 오른쪽 위치

    Solution(){}
    Solution(int sz, ll cost, int base, int del, int add): sz(sz), cost(cost), base(base), del(del), add(add){}

    bool operator<(const Solution &r)const{
        if(sz != r.sz) return sz < r.sz;
        return cost > r.cost;
    }
};
priority_queue<Solution> pq;

void makeAns(int row){
    for(int i=1; i<=n; i++){
        if(used[row][i]) sz[row]++, cost[row] += arr[i].v;
    }
}

struct segTree{
    int minV[1<<12], minIdx[1<<12];
    int lazy[1<<12];

    void merge(int i){
        minV[i] = min(minV[i*2], minV[i*2+1]);
        minIdx[i] = max(minV[i*2] == minV[i] ? minIdx[i*2] : 0,
                        minV[i*2+1] == minV[i] ? minIdx[i*2+1] : 0);
    }

    void init(int i, int l, int r){
        lazy[i] = 0;
        if(l==r){
            minV[i] = l, minIdx[i] = l;
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
        merge(i);
    }

    void propagate(int i, int l, int r){
        minV[i] += lazy[i];
        if(l!=r) lazy[i*2] += lazy[i], lazy[i*2+1] += lazy[i];
        lazy[i] = 0;
    }

    void update(int i, int l, int r, int s, int e, int v){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            lazy[i] += v;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i*2, l, m, s, e, v);
        update(i*2+1, m+1, r, s, e, v);
        merge(i);
    }

    pair<int, int> query(int i, int l, int r){
        propagate(i, l, r);
        return make_pair(minV[i], minIdx[i]);
    }
} tree;

void putPQ(int row){
    tree.init(1, 1, n);
    for(int i=1; i<=n; i++) if(used[row][i]) tree.update(1, 1, n, arr[i].d, n, -1);

    ll hsh = 0;
    for(int i=1; i<=n; i++) if(used[row][i]) hsh ^= RAND[i];
    if(row == 1) usedSets.insert(hsh);

    vector<pair<ll, ll> > nxtCand;
    for(int a=n; a>=1; a--){
        if(!used[row][a]){
            while(!nxtCand.empty() && nxtCand.back().first <= arr[a].d) nxtCand.pop_back();
            nxtCand.push_back({arr[a].d, a});
            continue;
        }
        tree.update(1, 1, n, arr[a].d, n, 1);
        pair<int, int> p = tree.query(1, 1, n);
        tree.update(1, 1, n, arr[a].d, n, -1);

        int minD = (p.first == 0 ? p.second+1 : 1);
        auto it = upper_bound(nxtCand.begin(), nxtCand.end(), make_pair(minD, 0), greater<pair<int, int> >());
        int minLoc = (it == nxtCand.begin() ? -1 : prev(it)->second);

        if(minLoc != -1){ // 대체
            ll newHsh = hsh ^ RAND[a] ^ RAND[minLoc];
            if(usedSets.count(newHsh)) continue;
            pq.push(Solution(sz[row], cost[row] - arr[a].v + arr[minLoc].v, row, a, minLoc));
            usedSets.insert(newHsh);
        }
        else{ // 삭제
            ll newHsh = hsh ^ RAND[a];
            if(usedSets.count(newHsh)) continue;
            pq.push(Solution(sz[row]-1, cost[row] - arr[a].v, row, a, 0));
            usedSets.insert(newHsh);
        }
    }
}

void getFromPQ(int row){
    assert(!pq.empty());
    Solution p = pq.top(); pq.pop();
    int base = p.base;
    copy(used[base]+1, used[base]+n+1, used[row]+1);
    used[row][p.del] = 0;
    if(p.add) used[row][p.add] = 1;
}

int main(){
    #ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    #endif

    uniform_int_distribution<ll> distrib(LLONG_MIN, LLONG_MAX);
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

    cin >> n >> k;
    for(int i=1; i<=n; i++){
        cin >> arr[i].v >> arr[i].d;
        RAND[i] = distrib(rng);
    }

    sort(arr+1, arr+n+1, [](Product &A, Product &B){
        return A.v < B.v;
    });

    // get best solution
    {
        vector<int> cnt (n+2);
        for(int i=1; i<=n; i++){
            cnt[arr[i].d]++;
            int s = 0, able = 1;
            for(int j=1; j<=n; j++){
                s += cnt[j];
                if(s > j){
                    able = 0;
                    break;
                }
            }

            if(able) used[1][i] = 1;
            else cnt[arr[i].d]--;
        }
    }

    makeAns(1);
    putPQ(1);
    for(int turn=2; turn<=k; turn++){
        getFromPQ(turn);
        makeAns(turn);
        putPQ(turn);
    }

    for(int i=1; i<=k; i++){
        cout << sz[i] << ' ' << cost[i] << '\n';
    }
}