초직사각형 (JUNGOL 4729)

https://jungol.co.kr/problem/4729

---

아이디어

그리디 알고리즘이 통합니다. 현재 상태에서 초부피를 가장 크게 증가시킬 수 있는 카드를 사용하는것을 $K$번 반복해주면 됩니다.

 

증명)

현재 A,B,C,D의 값이 순서대로 $A,B,C,D$라고 해봅시다. 그리고 현재 카드중에서 초부피를 가장 크게 증가시킬 수 있는 카드를 $M$이라고 해봅시다. 일반성을 잃지않고, $M$은 A를 $V_M$만큼 증가시킨다고 해봅시다.

 

만약 이 카드가 쓰이지 않는 최적해가 있다고 가정해봅시다. 그러면 A를 증가시키는 카드는 없음을 알 수 있습니다. A를 증가시키는 카드가 있다면, 그 카드를 $M$으로 교체하여 최적해를 키울 수 있기 때문입니다. 그러므로 사용하는 카드들은 B,C,D를 키우는 카드입니다.

 

남아있는 카드중 하나를 골라서 $L$이라 해봅시다. 일반성을 잃지않고 이 카드는 B를 $V_L$만큼 키운다고 해봅시다. 이때 $M$의 정의에 의해서 $V_MBC D \ge AV_LCD$입니다. 만약 $M$과 $L$을 제외한 모든 카드를 사용했다고 가정할 때, B,C,D가 각각 $b,c,d$만큼 증가했다고 해봅시다. 그러면 현재 부피는 $A(B+b)(C+c)(D+d)$입니다. 그리고, $L$을 사용하는것이 $M$을 사용하는것보다 더 좋은 결과를 가져오므로 $AV_L(C+c)(D+d)>V_M(B+b)(C+c)(D+d)$입니다. 이때 두 부등식을 정리하면, 두 식이 모두 참이 될 수 없습니다. 그러므로 이 결과는 모순입니다.

 

그러므로 A,B,C,D에 대해서 각 값을 증가시켜주는 카드를 크기가 큰 순서대로 정렬한 다음에, 4개의 카드 중 어떤 카드를 사용할지 골라주면 됩니다. 이때 수의 범위가 long long의 범위를 넘어갈 수 있으므로 __int128을 사용해주면 됩니다.

---

소스코드

#include <iostream>
#include <queue>
#include <algorithm>
#define ll __int128
using namespace std;


int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,K,i,A,B,C,D;
    char type;
    priority_queue <ll> cardA,cardB,cardC,cardD;

    long long tN,tK,tA,tB,tC,tD,x;
    cin>>tN>>tK>>tA>>tB>>tC>>tD;
    N=tN,K=tK,A=tA,B=tB,C=tC,D=tD;

    for (i=0;i<N;i++)
    {
        cin>>type>>x;
        if (type=='A') cardA.push(x);
        if (type=='B') cardB.push(x);
        if (type=='C') cardC.push(x);
        if (type=='D') cardD.push(x);
    }

    while (K--)
    {
        ll nowA=0,nowB=0,nowC=0,nowD=0;

        if (cardA.size()) nowA=cardA.top();
        if (cardB.size()) nowB=cardB.top();
        if (cardC.size()) nowC=cardC.top();
        if (cardD.size()) nowD=cardD.top();

        ll insA=nowA*B*C*D,insB=A*nowB*C*D,insC=A*B*nowC*D,insD=A*B*C*nowD;
        ll mx=max({insA,insB,insC,insD});
        
        if (insA==mx) A+=nowA,cardA.pop(),cout<<"A "<<(long long)nowA<<"\n";
        else if (insB==mx) B+=nowB,cardB.pop(),cout<<"B "<<(long long)nowB<<"\n";
        else if (insC==mx) C+=nowC,cardC.pop(),cout<<"C "<<(long long)nowC<<"\n";
        else if (insD==mx) D+=nowD,cardD.pop(),cout<<"D "<<(long long)nowD<<"\n";
    }
}