Little Piplup 7월 24일 팀연습

3시간 짜리 셋인 ACM-ICPC 2016 Daejeon Preliminary 를 돌았다.

백준 온라인 저지 에는 팀 계정 기능이 없기 때문에, 3PC 연습을 위해 팀원 각자 계정으로 같이 돌았다.

(1PC일때는 아무 계정이나 잡고 쓰면 되지만 이렇게 하면 제출 기록이 분산된다는 단점이 있기는 하다.)

 

제출 기록이 분산되면 코드를 볼 수가 없다.

다시 짜서 맞춰야 하는데, 너무 짜기 싫은게 몇개 있으므로 그 문제들은 BOJ 제출번호만 적었다 (언젠가 짜고 나면 돌아와서 추가하자) 

 

문제 링크 : https://www.acmicpc.net/category/detail/1528

 

K. 등록 을 제외하고, 푼 7문제를 AC 순서 (I-A-J-L-D-F-B) 순서로 풀이 작성한다.

---

I. Q-index

Solve : Gratus907

Code : Gratus907

제일 쉬운 문제를 먼저 찾기 위해 일단 한국어 문제지가 제공되는 문제를 읽었다.

무슨 말인지 처음에 독해가 잘 안 되긴 했지만, 아무튼 요점은 $k$ 이상의 수가 적어도 $k$개 있고, 나머지 $n-k$개 이상의 수가 $n-k$ 이하인 적당한 $k$를 찾으면 된다. $n$ 까지의 모든 $k$를 시도해도 $\mathcal{O}(n^2)$ 으로, 시간이 넉넉하므로 그대로 하면 된다.

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define bigprime (int)1e9+7
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

vector <int> paper;
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i<n; i++)
    {
        int x;
        cin >> x;
        paper.push_back(x);
    }
    for (int i = 0; i<=n; i++)
    {
        int a = 0;
        int b = 0;
        for (auto it:paper)
        {
            if (it>=i)
                a++;
            if (it<=i)
                b++;
        }
        if (a >= i && b >=(n-i))
        {
            cout << i;
            return 0;
        }
    }
}

이상 과 이하 에 주의해야 한다. (두 번 세야 하는게 있다)

---

A. 이진 트리

Solve : Coffeetea, Diordhd

Code : Diordhd

이진 트리에서, 루트로부터 모든 리프까지의 거리가 모두 같도록 간선의 길이를 적당히 늘려주는 문제.

아래로 재귀적으로 타고 내려가면서, 왼쪽 서브트리의 간선 길이의 총합과 오른쪽 서브트리의 간선 길이의 총합이 같도록 그리디하게 간선을 늘려주면 항상 답을 얻을 수 있다.

말로 들었을때는 어떻게 짜지 싶었는데, 나는 L번을 보고 있었기 때문에 일단 넘어갔다. 그래도 별 문제없이 잘 짠 거 같았다.

 

채점번호 14123572

---

J. 철로

Solve : Coffeetea

Code : Coffeetea

이때 세명이 각자 한문제씩 잡고 풀었는데, 다행히 셋 다 문제를 잘 골라서 빠르게 해결할 수 있었다.

$n$명의 사람들이 각각 $(a_i, b_i)$ 사이를 오가기 위해, 길이가 $L$ 인 철로를 잘 깔아서 최대한 많은 사람들이 오갈 수 있게 하는 문제.

나는 문제를 제대로 고민해 보진 않았는데, Coffeetea가 "Priority Queue 에 잘 넣었다 빼면서 세면 된다" 라고 풀고 AC를 받았다.

 

채점번호 14124337

---

L. 트럭

Solve : Gratus907, Diordhd 

Code : Gratus907

트럭 $n$ 대가 길이가 $w$ 인 다리를 지나려고 하는데, 한번에 무게가 $L$ 이상 올라가서는 안 된다.

모든 트럭이 순서대로 다리를 건너는 최단 시간을 찾는 문제.

 

트럭 순서를 바꿔서 뭔가를 얻을 수 없으므로 그냥 그리디하게 찾아내면 된다. 가장 무거운 트럭이라도 한 대는 반드시 올라갈 수 있음이 보장되어 있기 때문에, 아무리 많이 걸려도 $nw$ 시간이면 반드시 모든 트럭이 지나갈 수 있음을 이용, Queue에 넣으면서 무게를 추가하고 빼면서 무게를 빼는 식으로 구현하면 $\mathcal{O}(nw)$ 시간에 해결.

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define bigprime (int)1e9+7
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int n, w, l;
int weight[1010];
queue<pii> q; //weight, time;
int qsum;
int main()
{
    usecppio
    cin >> n >> w >> l;
    int tw = 0;
    for (int i = 0; i<n; i++)
    {
        int ww;
        cin >> ww;
        weight[i] = ww;
    }
    int ti = 0;
    int t = 0;
    int arriv = 0;
    for (t = 0; t<101010; t++)
    {
        if (!q.empty())
        {
            if (q.front().second <= t)
            {
                (qsum -= q.front().first);
                q.pop();
                arriv++;
                if (arriv == n)
                    break;
            }
        }
        if (ti<n)
        {
            if ((qsum + weight[ti]) <= l)
            {
                q.push({weight[ti], t + w});
                qsum += weight[ti];
                ti++;
            }
        }
    }

    cout << t+1 << '\n';
}

---

D. Message Passing

Solve : Diordhd

Code : Gratus907

문제를 안 읽어보고 코딩했는데 (...) 

Diordhd 가 내가 L번 구현하는동안 문제를 다 풀어서, 식을 다 적어 주고 이거 그냥 행렬 제곱 계산하면 된다 라고 주장했다.

코딩이 내가 조금 더 빠를 것 같아서 일단 내가 구현을 하기로 하고, 식을 받았는데 그냥 진짜 $d \times d$ 행렬 $t$제곱하는 문제길래 그냥 짜서 넘겼다.

이런 행렬 $D$에 대해서 

$$D = \begin{pmatrix}
1 & 1 & 0 & 0 & \dots \\
1 & 0 & 1 & 0 & \dots \\
1 & 0 & 0 & 1 & \dots \\ 
1 & 0 & 0 & 0 & \dots\\
\end{pmatrix}$$

$D^t$의 첫 행의 합을 구하면 되는 문제.

#include <bits/stdc++.h>
#define int ll
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define bigprime (int)1e9+7
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int mod = 31991;
int d, t;
struct matrix
{
    int n;
    int data[55][55];
    matrix(int n)
    {
        for (int i = 0; i<55; i++)
        {
            for (int j = 0; j<55; j++)
            {
                this->data[i][j] = 0;
            }
        }
    }
};

matrix identity(int n)
{
    matrix A =  matrix(n);
    for (int i = 0; i<n; i++)
        A.data[i][i] = 1;
    return A;
}

matrix matmul(matrix &A, matrix &B)
{
    matrix newmat = matrix(0);
    for (int i = 0; i<55; i++)
    {
        for (int j = 0; j<55; j++)
        {
            int x = 0;
            for (int k = 0; k<55; k++)
            {
                x += A.data[i][k] * B.data[k][j];
                x %= mod;
            }
            x %= mod;
            newmat.data[i][j] = x;

        }
    }
    return newmat;
}

matrix fastexpo(int b, matrix & mat)
{
    matrix result = identity(d);
    matrix km = mat;
    while(b)
    {
        if (b&1)
        {
            result = matmul(result,km);
            b--;
        }
        b /= 2;
        km = matmul(km, km);
    }
    return result;
}
int32_t main()
{
    usecppio
    cin >> d >> t;
    matrix M = matrix(d);
    for (int i = 0; i<d; i++)
        M.data[i][0] = 1;
    for (int i = 1; i<d; i++)
        M.data[i-1][i] = 1;
    M = fastexpo(t-1,M);
    int final = 0;
    for (int i = 0; i<d; i++)
    {
        final += M.data[0][i];
        final %= mod;
    }
    cout << final;
}

---

F. 유사 팰린드롬 

Solve : Coffeetea, Diordhd

Code : Diordhd 

사실 무슨 문제인지 잘 모르겠다. 나는 이때 B번에 집중하고 있었기 때문에...

일단 아무튼 dp 문제고, $n^2$ dp를 해야하는데 $n = 10,000$ 이니까 GCC Ofast 붙이고 기도하겠다 라고 대충 둘이 풀이 완성하고 코딩하는거 같길래 뭐 되겠지 라고 생각했다. 원래 1억보다 좀 더 돌아가기도 하고 모르면 일단 기도메타가 정답이니까

 

1728ms로 맞았던데, Ofast 안붙였으면 TLE 났을 수도 있을 거 같다. Ofast로 빨라지는 연산을 쓴게 맞는지는 잘 모르겠지만.

 

채점번호 14126378

---

B. Diameter

Solve : Gratus907, Diordhd, Coffeetea

Code : Gratus907

$n$ 개의 점이 주어지는데, 이 점을 두 개의 그룹으로 나눈다. 이때, 각 그룹의 Diameter (지름) 은 각 그룹 내의 두 점 거리의 최댓값이다.

Diameter의 합을 최소화하는 방법을 제시하는 문제.

 

다음을 먼저 관찰한다.

관찰 1. 가장 먼 두 점은 서로 다른 그룹에 들어가야 한다. 

만약 가장 먼 두 점이 서로 같은 그룹에 들어가 있다면, 그 그룹의 지름이 그 두 점 사이 거리 $d$ 이다. 그런데, 가장 먼 두 점을 $i, j$ 번 점이라고 할 때, $j$번을 제외한 나머지 모든 점 // $j$번 이런 식으로 그룹을 나누면, 첫 그룹의 지름은 $d$보다 작고 두 번째 그룹의 지름은 0이므로 합이 $d$보다 작다. 따라서, 두 점이 서로 같은 그룹에 들어가는 것은 절대 해가 될 수 없다.

 

이제, 가장 먼 두 점을 $i, j$번이라고 할 때, 나머지 모든 점들을 $i$번 점에 가까운 순서대로 정렬하자. 

배열 A를 선언해서, $i$번에 가까운 점들을 그룹 1에 밀어 넣으면서 그룹 1의 지름의 변화를 $n$개까지 모두 넣으면서 관찰한다. 이 과정은 한 점을 추가할 때, 추가한 점들과 나머지들의 거리만 보면 되므로 $\mathcal{O}(n^2)$ 에 수행 가능하다.

반대로, $i$번에 먼 점들을 그룹 2에 밀어 넣으면서 배열 B를 갱신한다. 

이제, $t$ 를 0부터 $n-1$ 까지 올리면서 $A[t] + B[t+1]$ 의 최솟값을 찾는다.   

#include <bits/stdc++.h>
#define int ll
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define bigprime (int)1e9+7
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int dist1cand[5050];
int dist2cand[5050];
int xcord[5050], ycord[5050];
int ind[5050];
int p1 = 1;
int p2 = 2;
int curmax;
int dist(int a, int b)
{
    return (xcord[a]-xcord[b])*(xcord[a]-xcord[b]) + (ycord[a]-ycord[b])*(ycord[a]-ycord[b]);
}
bool comp(int a, int b)
{
    return (dist(a,p1) < dist(b,p1));
}
int32_t main()
{
    int n;
    cin >> n;
    for (int i = 1; i<=n; i++)
    {
        int x, y;
        cin >> x >> y;
        xcord[i] = x;
        ycord[i] = y;
    }
    for (int i = 1; i<=n; i++)
    {
        for (int j = 1; j<=n; j++)
        {
            ll u = dist(i,j);
            if (u> curmax)
            {
                curmax = u;
                p1 = i, p2 = j;
            }
        }
    }
    for (int i = 1; i<=n; i++)
        ind[i] = i;
    sort(ind+1,ind+(n+1),comp);
    for (int i = n; i>0; i--)
    {
        dist2cand[i] = dist2cand[i+1];
        for (int j = n; j>i; j--)
        {
            dist2cand[i] = max(dist2cand[i], dist(ind[i],ind[j]));
        }
    }
    int forward_maximum = 0;
    for (int i = 1; i<n; i++)
    {
        dist1cand[i] = dist1cand[i-1];
        for (int j = 1; j<i; j++)
        {
            dist1cand[i] = max(dist1cand[i], dist(ind[i],ind[j]));
        }
    }
    double ans = 3e15;
    for (int i = 1; i<n; i++)
    {
        ans = min(ans, sqrt((double)dist1cand[i]) + sqrt((double)dist2cand[i+1]));
    }
    cout << setprecision(10) << ans;
    
}