[업솔빙] ICPC 2018 풀이 Part 2

　이전 포스트: “[업솔빙] ICPC 2018 풀이 Part 1”

　이 글에서는 Part 1에서 다루지 못한 나머지 5문제의 풀이를 서술합니다.

　B. Cosmetic Survey

　티어: 플래티넘 IV

　후술할 J번과 더불어 지문 해석이 상당히 어려웠던 문제였는데, 문제 내용을 요약하면 다음과 같습니다.

\( d(X, Y) \)를 X번 정점(화장품)을 Y번 정점(화장품)보다 더 좋게 평가한 사람 수로 정의한다.
\( d(X, Y) > d(Y, X) \)라면 \( X \)에서 \( Y \)로 가는 가중치 \( d(X, Y) \)인 간선이 있다고 간주한다.
\( S(X, Y) \)를 \( X \)에서 \( Y \)로 가는 각 경로의 \( d(X, Y) \)의 최솟값들 중 최댓값으로 정의한다.
화장품 X를 가장 선호한다는 것은, 모든 화장품 \( Y( \ne X) \)에 대해, \( S(X, Y) \ge S(Y, X) \)를 만족한다는 것을 의미한다.
이때, (평가자들이)가장 선호하는 화장품을 모두 찾아라.

　풀이는 간단합니다. 모든 \( (X, Y) \)쌍에 대해 \( d(X, Y) \)와 \( d(Y, X) \)를 비교해서 간선을 구성한 후, 플로이드-와샬을 돌리면 \( O(n^3) \)에 풀 수 있습니다.

　코드;

#include<cstdio>
#include<vector>
#include<algorithm>
#define inf ((int)1e9)

using namespace std;

vector<int> v[510];

int arr[510][510];
int dist[510][510];

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            scanf("%d",arr[j]+i);
            if(!arr[j][i])arr[j][i]=inf;
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=i+1;j<=n;++j){
            int l=0,r=0;
            for(int k=1;k<=m;++k){
                if(arr[i][k]==arr[j][k])continue;
                arr[i][k]<arr[j][k]?++l:++r;
            }
            if(l==r)continue;
            l<r?dist[j][i]=r:dist[i][j]=l;
        }
    }
    for(int k=1;k<=n;++k){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                if(!dist[i][k]||!dist[k][j])continue;
                dist[i][j]=max(dist[i][j],min(dist[i][k],dist[k][j]));
            }
        }
    }
    for(int i=1;i<=n;++i){
        bool flag=false;
        for(int j=1;j<=n;++j){
            if(i==j)continue;
            if(dist[i][j]<dist[j][i]){
                flag=true;
                break;
            }
        }
        if(!flag)printf("%d ",i);
    }
}

　G. Secret Code

　티어: 플래티넘 II

　일반성을 잃지 않고, \( t_a \le t_b \le t_c \)라고 가정합시다. 그렇다면, 우리가 알고자 하는 것은 아래의 세 가지 조건을 만족할 확률이 됩니다.

\( 0 \le t_a \le t_b \le t_c \le S\)
\( t_a \le t_b \le t_a+w_a \)
\( t_b \le t_c \le t_b+w_b \)

　이는 포함 배제의 원리에 의해 첫 번째 조건을 만족할 확률에서 두 번째 또는 세 번째 조건을 만족하지 않을 확률을 뺀 것이고, 이는 \( t_b > t_a+w_a \)이거나 \( t_c > t_b+w_b \)일 확률, 여기서 포함 배제 원리를 한번 더 사용하면, \( t_b > t_a+w_a \)일 확률 + \( t_c > t_b+w_b \) - \( t_b > t_a+w_a, t_c > t_b+w_b \)일 확률이 됩니다. 지금까지 말한 것을 적분식으로 나타내면 다음과 같습니다.

\( \frac{1}{S^3}( \frac{S^3}{6} - \int_{0}^{S-w_a} \int_{x_1+w_a}^{S} \int_{x_2}^{S} \ dx_3\ dx_2\ dx_1 - \int_{0}^{S-w_b} \int_{x_1}^{S-w_b} \int_{x_2+w_b}^{S} \ dx_3\ dx_2\ dx_1 + \int_{0}^{S-w_a-w_b} \int_{x_1+w_a}^{S-w_b} \int_{x_2+w_b}^{S} \ dx_3\ dx_2\ dx_1) \)

　그리고 이 적분식을 풀면 \( \frac{1}{S^3} (\frac{S^3}{6} - \frac{(S-w_a)^3}{6} - \frac{(S-w_b)^3}{6} + \frac{(S-w_a-w_b)^3}{6}) \)이 되고, 같은 방식으로 나머지 5가지 경우 (\( t_a \le t_c \le t_b \)일 경우 등)에 대해서도 처리해 주면, \( \frac{1}{S^3} (\frac{S^3}{6} - \frac{2(S-w_a)^3}{3} - \frac{2(S-w_b)^3}{3} + \frac{(S-w_a-w_b)^3}{3}) \)이 됩니다. 이 값이 작은 순서대로(같다면 인덱스가 작은 순서대로) 정렬하면 됩니다.

　코드

　혹시 모를 부동소수점 오차 문제를 피하기 위해, 실수 연산을 모두 정수 연산으로 대체했으니, 이점 참고바랍니다.

#include<cstdio>
#include<algorithm>

using namespace std;
using ld=long double;
using ll=long long;

struct Node{
    ll nu,de;
    ll s,idx,w[3];
};

Node arr[30];

ll pow3(ll a){
    return a*a*a;
}

bool cmp(Node& a,Node& b){
    if(a.nu*b.de-a.de*b.nu)return a.nu*b.de<a.de*b.nu;
    return a.idx<b.idx;
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%lld %lld %lld %lld",&arr[i].s,arr[i].w,arr[i].w+1,arr[i].w+2);
        arr[i].idx=i;
        arr[i].nu=arr[i].de=3*pow3(arr[i].s);
        arr[i].nu-=2*pow3(arr[i].s-arr[i].w[0]);
        arr[i].nu-=2*pow3(arr[i].s-arr[i].w[1]);
        arr[i].nu-=2*pow3(arr[i].s-arr[i].w[2]);
        arr[i].nu+=pow3(arr[i].s-arr[i].w[0]-arr[i].w[1]);
        arr[i].nu+=pow3(arr[i].s-arr[i].w[1]-arr[i].w[2]);
        arr[i].nu+=pow3(arr[i].s-arr[i].w[0]-arr[i].w[2]);
    }
    sort(arr,arr+n,cmp);
    for(int i=0;i<n;++i)printf("%d ",arr[i].idx+1);
}

　C. Disks Arrangement

　티어: 다이아몬드 V

　모든 valid한 배치에 대해서, i번째로 배치된 디스크의 반지름을 \( D_i \)라 했을 때, 피타고라스 정리를 사용하면, 디스크들의 가로 길이의 합은 \( D_1 + 2 \sqrt{D_1 D_2} + 2 \sqrt{D_2 D_3} + … + 2 \sqrt{D_{n-1} D_{n}} + D_n \)임을 쉽게 알 수 있습니다. 추가로, 반지름이 가장 긴 디스크의 반지름이 반지름이 가장 짧은 디스크의 반지름의 4배 이하라는 조건으로 인해, 모든 배치는 valid함을 알 수 있습니다.

　이제 남은 건 n이 작을때의 규칙을 찾아서 적용하는 것 뿐인데, 제가 찾은 규칙은 다음과 같습니다.

n이 짝수일 때
- 홀수 번째에는 덱(deque)의 맨 앞에 남은 디스크 중 반지름이 가장 짧은 디스크를, 맨 뒤에는 남은 디스크 중 반지름이 가장 긴 디스크를 삽입한다.
- 짝수 번째에는 덱의 맨 앞에 (남은 디스크 중) 반지름이 가장 긴 디스크를, 맨 뒤에는 반지름이 가장 짧은 디스크를 삽입한다.
n이 홀수일 때
- 우선 덱에 반지름이 가장 짧은 디스크를 삽입한다.
  - 홀수 번째에는 덱의 맨 앞에 남은 디스크 중 반지름이 두 번째로 긴 디스크를, 맨 뒤에는 남은 디스크 중 반지름이 가장 긴 디스크를 삽입한다.
  - 짝수 번째에는 덱의 맨 앞에 (남은 디스크 중) 반지름이 두 번째로 짧은 디스크를, 맨 뒤에는 반지름이 가장 짧은 디스크를 삽입한다.
- 덱을 모두 비우고, 이번에는 덱에 반지름이 가장 긴 디스크를 삽입한다.
  - 홀수 번째에는 덱의 맨 앞에 남은 디스크 중 반지름이 두 번째로 짧은 디스크를, 맨 뒤에는 반지름이 가장 짧은 디스크를 삽입한다.
  - 짝수 번째에는 덱의 맨 앞에 남은 디스크 중 반지름이 두 번째로 긴 디스크를, 맨 뒤에는 남은 디스크 중 반지름이 가장 긴 디스크를 삽입한다.
- 두 경우의 가로 길이를 비교하여, 더 짧은 것을 출력한다.

　증명은 나중에 알게되면 추가하도록 하겠습니다.

　코드

#include<cstdio>
#include<cmath>
#include<deque>
#include<algorithm>

using namespace std;
using ll=long long;
using ld=long double;

int arr[1010];

deque<int> dq;

int main(){
    int n;
    ld ans,cur;
    scanf("%d",&n);
    for(int i=0;i<n;++i)scanf("%d",arr+i);
    sort(arr,arr+n);
    if(n&1){
        dq.push_front(arr[0]);
        for(int i=1;i<=n/2;++i){
            if(i&1){
                dq.push_front(arr[n-i]);
                dq.push_back(arr[n-i-1]);
            }
            else{
                dq.push_front(arr[i-1]);
                dq.push_back(arr[i]);
            }
        }
        ans=dq[0]+dq[n-1];
        for(int i=1;i<n;++i)ans+=2*sqrtl((ll)dq[i]*dq[i-1]);
        dq.clear();
        dq.push_back(arr[n-1]);
        for(int i=0;i<n/2;++i){
            if(i&1){
                dq.push_front(arr[n-i-2]);
                dq.push_back(arr[n-i-1]);
            }
            else{
                dq.push_front(arr[i+1]);
                dq.push_back(arr[i]);
            }
        }
        cur=dq[0]+dq[n-1];
        for(int i=1;i<n;++i)cur+=2*sqrtl((ll)dq[i]*dq[i-1]);
        printf("%.10Lf",min(ans,cur));
    }
    else{
        for(int i=0;i<n/2;++i){
            if(i&1){
                dq.push_front(arr[n-i-1]);
                dq.push_back(arr[i]);
            }
            else{
                dq.push_front(arr[i]);
                dq.push_back(arr[n-i-1]);
            }
        }
        ans=dq[0]+dq[n-1];
        for(int i=1;i<n;++i)ans+=2*sqrtl((ll)dq[i]*dq[i-1]);
        printf("%.10Lf",ans);
    }
}

　E. LED

　티어: 플래티넘 IV

　입력으로 들어온 \( (v_i, l_i) \) 쌍을 \( v_i \) 기준으로 정렬하고, 이분 탐색을 통해 \( F(v) = L_1\)인 구간의 시작점을 정하고, 선형 탐색을 통해 \( F(v) = 0\)인 구간의 오차의 최댓값, \( F(v) = L_1\)또는 \( F(v) = L_2\)인 구간의 오차의 최댓값을 비교하면서 최적의 \( F(v) = L_1\) 구간의 시작점을 찾으면 \( O(n \log n) \) 에 문제를 해결할 수 있습니다.

　다만 주의해야 할 것이, \( v_i = 0 \)인 데이터가 있다면, 해당 데이터는 반드시 \( F(v) = 0\) 구간에 속해야 합니다.

　<코드>

#include<cstdio>
#include<cassert>
#include<algorithm>
#define inf 2e9
#define x first
#define y second

using namespace std;
using pii=pair<int,int>;

pii arr[300010];
int mx[300010],rmn[300010],rmx[300010];

int main(){
    int n,ans=inf+2,lcur,rcur;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d %d",&arr[i].x,&arr[i].y);
    sort(arr+1,arr+n+1);
    int s=0,e=n;
    if(arr[1].x==0)s=1;
    for(int i=1;i<=n;++i)mx[i]=max(mx[i-1],arr[i].y);
    rmn[n]=rmx[n]=arr[n].y;
    for(int i=n-1;i>=0;--i)rmn[i]=min(rmn[i+1],arr[i].y),rmx[i]=max(rmx[i+1],arr[i].y);
    while(s<=e){
        int m=s+e>>1,lmn=inf,lmx=0;
        lcur=mx[m]*2;
        for(int i=m;i<=n;++i){
            if(i==m){
                rcur=rmx[m+1]-rmn[m+1];
                continue;
            }
            lmn=min(lmn,arr[i].y),lmx=max(lmx,arr[i].y);
            if(i==n){
                rcur=min(rcur,lmx-lmn);
                continue;
            }
            if(lmx+lmn>rmx[i+1]+rmn[i+1])rcur=min(rcur,max(lmx,rmx[i+1])-min(lmn,rmn[i+1]));
            else rcur=min(rcur,max(lmx-lmn,rmx[i+1]-rmn[i+1]));
        }
        ans=min(ans,max(lcur,rcur));
        if(lcur==rcur)break;
        if(lcur>rcur)e=m-1;
        else s=m+1;
    }
    printf("%d.%d\n",ans/2,(ans&1)?5:0);
}

　J. Starwars

　티어: 플래티넘 IV

　BFS를 통해 문제를 해결할 수 있습니다. 우선, 큐에 모든 (인간 행성, 외계 행성) 쌍을 추가해 놓습니다. 그리고 큐가 비어있게 될 때까지 다음 과정을 반복합니다.

큐에서 원소(pair)를 하나 꺼냅니다. (l, r)이라고 해두겠습니다.
l과 r이 둘다 군사 지역이라면, 인간 행성/외계 행성에서 같은 sequence로 군사 지역까지 도달할 수 있다는 의미이므로, 즉시 YES를 출력하고 프로그램을 종료합니다.
l번 행성과 r번 행성의 모든 간선 쌍에 대하여, 받는 증명서의 종류가 같고, 해당 pair를 큐에 집어넣은 적이 없다면, 큐에 추가합니다.

　이렇게 풀면 해당 문제를 \( O(\Sigma {d_i d_j}) = O(\Sigma ({d_i \Sigma {d_j}})) = O(m^2)\)에 해결할 수 있습니다.

　코드

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;
using pii=pair<int,int>;

int visit[1010][1010];
vector<pii> graph[1010];
int human[1010],mil[1010];
vector<int> hs,ns;
queue<pii> q;

int main(){
    int n,w,c,h,m,tmp,s,t,e;
    scanf("%d %d %d %d %d",&n,&w,&c,&h,&m);
    for(int i=0;i<h;++i){
        scanf("%d",&tmp);
        human[tmp]=1;
    }
    for(int i=0;i<m;++i){
        scanf("%d",&tmp);
        mil[tmp]=1;
    }
    for(int i=0;i<w;++i){
        scanf("%d %d %d",&s,&t,&e);
        graph[s].push_back({e,t});
    }
    for(int i=0;i<n;++i)human[i]?hs.push_back(i):ns.push_back(i);
    for(auto i:hs)for(auto j:ns)q.push({i,j}),visit[i][j]=1;
    while(q.size()){
        int x=q.front().first,y=q.front().second;
        q.pop();
        if(mil[x]&&mil[y]){
            printf("YES");
            return 0;
        }
        for(auto i:graph[x]){
            for(auto j:graph[y]){
                if(visit[i.first][j.first]||i.second!=j.second)continue;
                visit[i.first][j.first]=1;
                q.push({i.first,j.first});
            }
        }
    }
    printf("NO");
}