[USACO] 2018 January Contest (Silver) 풀이

1. [15589] Lifeguards (Silver)

• 문제 링크: https://www.acmicpc.net/problem/15589

• 문제 설명: $N$ 마리의 소가 1부터 10억 까지의 단위 시간 사이의 임의의 구간을 덮고 있다. 이 소들 중 한 마리를 제거할 때, 여전히 덮혀 있는 구간의 길이를 최대화 하는 문제이다.

• 문제 풀이: $N$의 범위가 10만밖에 되지 않으므로, 사용하는 좌표 역시 20만개를 초과하지 않는다. 따라서 정렬 및 좌표압축 후 스위핑 비슷하게 단 하나의 소만으로 덮혀 있는 구간과 하나 이상의 소로 덮혀 있는 구간의 길이를 prefix sum으로 계산해 주고, 이를 바탕으로 각 소를 한 번씩 제거해주면서 기존에는 덮혀 있었지만 이제 덮혀지지 않는 구간의 길이를 $O(1)$로 계산해 줄 수 있다. 따라서 총 시간복잡도는 $O(N lg N)$이다.
• 소스 코드:

#include <bits/stdc++.h>
 
using namespace std;
typedef pair<int,int> pii;
 
vector<int> v;
vector<pii> q;
int ps[200005];
int pss[200005];
int fps[200005];
 
int idx(int x){
    return lower_bound(v.begin(),v.end(),x)-v.begin();
}
 
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int t1,t2;
        scanf("%d %d",&t1,&t2);
        q.push_back(make_pair(t1,t2));
        v.push_back(t1); v.push_back(t2);
    }
    v.push_back(-1);
    sort(v.begin(),v.end());
    for(int i=0;i<n;i++){
        int le=idx(q[i].first),ri=idx(q[i].second);
        ps[le]++; ps[ri]--;
    }
    for(int i=1;i<=200000;i++)
        pss[i]=pss[i-1]+ps[i];
    for(int i=1;i<=200000;i++)
        fps[i]=fps[i-1]+(pss[i]==1?v[i+1]-v[i]:0);
    int ret=1e9+10;
    for(int i=0;i<q.size();i++){
        int le=idx(q[i].first),ri=idx(q[i].second);
        ret=min(ret,fps[ri-1]-fps[le-1]);
    }
    for(int i=1;i<=200000;i++)
        fps[i]=fps[i-1]+(pss[i]>=1?v[i+1]-v[i]:0);
    printf("%d",fps[200000]-ret);
    return 0;
}
 

2. [15590] Rental Service

• 문제 링크: https://www.acmicpc.net/problem/15590
• 문제 설명: $N$마리의 소가 있고, 각각의 소는 하루에 우유를 $c_i$만큼 생산한다. $M$개의 가게가 있어서 이 가게에서는 우유 1단위당 $p_i$ 만큼의 돈을 주고 최대 $q_i$단위까지 매입한다. 또 원한다면 $R$명의 다른 농부들에게 소를 빌려줄 수 있는데, 한 농부는 $r_i$가격에 최대 한 마리의 소를 빌려 간다. 이때 얻을 수 있는 최대의 수입을 구해야 한다.
• 문제 풀이: 일단 우유를 판다면 돈을 많이 주는 데부터 파는 게 이득이고, 소를 빌려 준다고 해도 돈을 많이 주는 데부터 빌려주는 게 이득이다. 또 소를 빌려 준다면 우유 생산량이 낮은 소부터 빌려 주는 것이 이득이다. 따라서 이것들을 모두 정렬한다. 그 후 모든 소들을 빌려준 다음 소를 하나씩 회수해 오면서 언제 수입이 가장 많은 지를 계산하면 된다. 
• 소스 코드:

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
ll c[100005],s[100005];
pair<ll,ll> p[100005];
 
int main(){
    int n,m,r;
    ll ans=0;
    scanf("%d %d %d",&n,&m,&r);
    for(int i=0;i<n;i++)
        scanf("%lld",&c[i]);
    for(int i=0;i<m;i++)
        scanf("%lld %lld",&p[i].second,&p[i].first);
    for(int i=0;i<r;i++)
        scanf("%lld",&s[i]);
    sort(c,c+n,greater<ll>());
    sort(p,p+m,greater<pair<ll,ll> >());
    sort(s,s+r,greater<ll>());
    for(int i=0;i<min(n,r);i++)
        ans+=s[i];
    int cnt=0;
    for(int i=0;i<n-min(n,r);i++){
        ll milk=c[i];
        while(milk){
            if(cnt>=m) break;
            ll buy=min(p[cnt].second,milk);
            ans+=buy*p[cnt].first;
            milk-=buy; p[cnt].second-=buy;
            if(!p[cnt].second) cnt++;
        }
    }
    ll ma=ans;
    for(int i=1;i<=min(n,r);i++){ // do not sell i cows
        ans-=s[min(n,r)-i];
        ll milk=c[n-min(n,r)+i-1];
        while(milk){
            if(cnt>=m) break;
            ll buy=min(p[cnt].second,milk);
            ans+=buy*p[cnt].first;
            milk-=buy; p[cnt].second-=buy;
            if(!p[cnt].second) cnt++;
        }
        ma=max(ma,ans);
    }
    printf("%lld",ma);
    return 0;
}
 

3. [15591] MooTube (Silver)

• 문제 링크: https://www.acmicpc.net/problem/15591
• 문제 설명: 정점이 $N$개인 루트 없는 트리가 주어질 때, 어떤 정점 $V$와 정수 $K$에 대해 $V$와의 경로 내 간선의 최소 가중치가 $K$ 이상인 정점의 개수를 구하는 쿼리를 $Q$개 해결하면 된다. $N$과 $Q$ 모두 5000 이내이다.
• 문제 풀이: 범위가 작으므로 각 쿼리마다 가중치가 K 미만인 간선을 무시한 채 정점에서 BFS를 돌려줄 수 있고, 이때 시간복잡도는 O(QN)이다.
  하지만...
• 조금 더 생각해보기 (MooTube Gold, 15586, https://www.acmicpc.net/problem/15586)
  사실 이 문제는 조금 더 빠르게 해결할 수 있다. 만약 정점이 10만개라면 어떠한 방식으로 해결해야 할까?
  우리가 해결하고 싶은 쿼리는 어떤 정점에서 가중치가 $K$ 미만인 간선만을 사용했을 때 방문할 수 있는 정점 개수를 빠르게 구하는 것이다. 이런 유형의 문제들에 대해서는 쿼리를 정렬하여 효율적으로 해결한다는 아이디어를 사용해 볼 수 있다. 모든 쿼리들을 가중치의 내림차순으로 정렬해 보자. 이 순서대로 쿼리를 처리한다면, 사용 가능한 간선들의 집합은 항상 늘어남을 알 수 있다. 이렇게 되면 문제는 어떤 $K$에 대하여 그 때 어떤 정점 $V$와 연결된 컴포넌트의 크기를 빠르게 찾는 문제로 바뀐다. 이는 어떤 정점들이 연결되어 있고 크기가 얼마인지 확인하는 것이고, Union-Find 트리를 통해 해결해 줄 수 있다. UF 트리의 노드 중 루트 노드들이 각 컴포넌트의 크기를 가지고 있도록 하면 간선이 생기면서 컴포넌트가 Merge 될 때 크기를 빠르게 계산해 줄 수 있다. 간선을 추가하는 작업은 최대 $O(N)$번 수행된다. 따라서 총 시간복잡도는 $O(Q lg Q+N)$이다.
• 소스 코드:

#include <bits/stdc++.h>
 
using namespace std;
typedef pair<int,int> pii;
 
vector<pair<int,pii> > edge;
vector<pair<pii,int> > query;
 
typedef struct DisJointSet{
    vector<int> p,sz;
    DisJointSet(int _n){
        p.resize(_n+1);
        sz.assign(_n+1,1);
        for(int i=0;i<=_n;i++) p[i]=i;
    }
    int fi(int x){
        if(p[x]==x) return x;
        else return p[x]=fi(p[x]);
    }
    void un(int a, int b){
        a=fi(a); b=fi(b);
        if(a==b) return;
        sz[b]+=sz[a];
        p[a]=b;
    }
    int node_size(int x) {return sz[fi(x)];}
}DSU;
 
int main(){
    int n,q;
    scanf("%d %d",&n,&q);
    for(int i=0;i<n-1;i++){
        int t1,t2,tw;
        scanf("%d %d %d",&t1,&t2,&tw);
        edge.push_back(make_pair(tw,make_pair(t1,t2)));
    }
    for(int i=0;i<q;i++){
        int t1,t2;
        scanf("%d %d",&t1,&t2);
        query.push_back(make_pair(make_pair(t1,t2),i));
    }
    DSU uf(n);
    sort(query.begin(),query.end(),[](const pair<pii,int> &a, const pair<pii,int> &b){
        return a.first.first>b.first.first;
    });
    sort(edge.begin(),edge.end(),greater<pair<int,pii> >() );
    int cnt=-1;
    for(int i=0;i<query.size();i++){
        int k=query[i].first.first;
        int v=query[i].first.second;
        while(cnt+1<edge.size() && edge[cnt+1].first>=k){
            cnt++;
            uf.un(edge[cnt].second.first,edge[cnt].second.second);
        }
        query[i].first.first=uf.node_size(v)-1;
    }
    sort(query.begin(),query.end(),[](pair<pii,int> a, pair<pii,int> b){
            return a.second<b.second;
    });
    for(int i=0;i<query.size();i++){
        printf("%d\n",query[i].first.first);
    }
    return 0;
}