백준 21761: 초직사각형

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

21761번: 초직사각형

 

풀이

적당히 눈에 보이는 그리디로 풀어주면 맞습니다. $ABCD$의 값을 최대로 변화시켜주는 카드를 계속 찾아주면 됩니다.

이 방법으로 최적해를 찾을 수 있다는 것을 증명해보겠습니다.

처음에 값이 $A,\ B,\ C,\ D$라고 하겠습니다. 첫 시행에서 초직사각형의 부피를 가장 많이 증가시켜주는 카드를 일반성을 잃지 않고 $A$를 $N$만큼 증가시켜주는 카드(이제부터 $X$라고 부르겠습니다)라 둡니다. $X$가 포함된 최적해가 존재한다는 것을 증명하기 위하여 귀류법으로 생각하여 $X$가 최적해에 포함되지 않는다고 가정합니다.

 

최적해의 카드 중에 $A$를 증가시켜주는 카드가 있을까요? 혹시라도 있다면, 그 카드를 $X$로 교체한다면 당연히 부피가 더 커지게 되므로 모순이 발생합니다. 따라서 최적해의 카드 중에서는 $A$를 증가시키는 카드가 없습니다.

 

최적해일 때의 카드 $K$개 중 한 개를 뽑아 그 카드의 이름을 $Y$라 하겠습니다. 또한, 일반성을 잃지 않고 그 카드를 $B$를 $L$만큼 증가시키는 카드라 두겠습니다. 카드를 사용하는 순서는 최종적으로 얻어내는 부피에 영향을 주지 않는다는 것이 자명하므로, $Y$를 뺀 나머지 $K-1$개의 카드를 모두 사용하여 $B$를 $b$만큼, $C$를 $c$만큼, $D$를 $d$만큼 증가시켜($b,\ c,\ d,\ \geq 0$) 현재 부피가 $A(B+b)(C+c)(D+d)$가 되었다 합시다. 여기에서 $Y$를 사용했다면, 부피 증가량 $\Delta V_Y=AL(C+c)(D+d)$가 됩니다. 여기에서 $X$를 사용했다면, 부피 증가량 $\Delta V_X=N(B+b)(C+c)(D+d)$가 됩니다. 이 둘의 공통인 인수를 제거하면 $AL$과 $N(B+b)$를 비교하는 것이 됩니다.

맨 위의 가정에서 $X$를 첫 시행에서 초직사각형의 부피를 가장 많이 증가시켜주는 카드로 두었기 때문에 $X$를 사용한 $ABCD$의 부피 증가량이 $Y$를 사용한 $ABCD$의 부피 증가량보다 커야 합니다. 이를 식으로 표현하면 $NBCD>ALCD$이며, $CD$로 나누어주면 $NB>AL$이 됩니다. 따라서 위에서 $AL<N(B+b)$가 되어 $K$번째에 $Y$를 사용하는 것보다 $X$를 사용하는 것이 더 크므로 가정에 모순이 발생하여 증명이 끝납니다.

 

위의 방법으로 그리디를 제한을 생각하지 않고 짜서 WA를 한 번 받았습니다. 처음에는 $\Delta V$를 비교하는 형식으로 했는데 오버플로우가 나서 $A,\ B,\ C,\ D$를 증가시키는 카드 4개에서 2개씩을 뽑아 비교해가며 쓸 카드를 정했습니다. 다른 분의 말씀을 들어 보니, $\frac{\Delta A}{A}$들을 비교하는 방식으로 하는 것이 편하다고 합니다.

 

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[4];
string s="ABCD";
pair<int, ll> ans[200001];
vector<ll> adj[4];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int k, n;
    cin >> n >> k;
    for(int i=0; i<4; i++) cin >> a[i];
    for(int i=0; i<n; i++) {
        string r;
        ll t;
        cin >> r >> t;
        adj[r[0]-'A'].push_back(t);
    }
    for(int i=0; i<4; i++) sort(adj[i].begin(), adj[i].end());
    for(int i=0; i<k; i++) {
        int idx;
        bool b[4];
        for(int j=0; j<4; j++) b[j]=!adj[j].empty();
        for(int j=0; j<4; j++) for(int l=j+1; l<4; l++) if(!adj[j].empty() && !adj[l].empty()) {
            ll p=adj[j].back(), q=adj[l].back();
            p*=a[l], q*=a[j];
            if(p>q) b[l]=0;
            else b[j]=0;
        }
        for(int j=0; j<4; j++) if(b[j]) idx=j;
        a[idx]+=adj[idx].back();
        ans[i]={idx, adj[idx].back()};
        adj[idx].pop_back();
    }
    for(int i=0; i<k; i++) cout << s[ans[i].first] << " " << ans[i].second << "\n";
}