Little Piplup 6월 24일 팀연습

Little Piplup 다섯 번째 팀연습. 

 

문제번호	B	E	F	G	H	I	K
문제 레이팅	1700	2200	1900	1800	2100	1900	2000
푼 시간	00:31 (+4)	03:43 (+2)	02:21 (+1)	00:58 (+2)	01:45	02:38	02:10

굉장히 팀워크가 잘 맞았는데도, Code가 Solve에 비해 너무 느려서 컴퓨터 병목이 상당했다.

초반 팀 전략이 개판났는데, 결국에는 이득을 봤다;;

---

풀이 (푼 순서)

B. Devu and Partitioning of the Array 

Solution : Coffeetea, Gratus907, Diordhd

Code : Gratus907

 

Diordhd 가 A번을 읽는 동안, bitwise and가 들어간 걸 보고 바로 손절해버리고 읽은 문제.

$n$개의 숫자를 $k$개의 부분 수열로 나눌 건데, 그중 $p$ 개는 합이 짝수여야 하고, $k-p$ 개는 합이 홀수여야 한다.

 

쉽게 해결하는 방법은, 일단 홀수를 다 만든 다음 (홀수를 최소한만 써서) 

마지막 부분수열에 다 때려넣으면 끝.

 

그런데 뭔가 구현에서 끝없이 뇌절하고 4틀한 후 30분 후에야 맞았다. 

#include <bits/stdc++.h>
using namespace std;

int n,k,p;
vector <int> seq[101010];
vector <int> even;
vector <int> odd;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> k >> p;
    for (int i = 0; i<n; i++)
    {
        int x;
        cin >> x;
        if (x%2)
            odd.push_back(x);
        else
            even.push_back(x); 
    }
    int a = odd.size();
    int u = k-p;
    if ((a>=(k-p) && ((a-(k-p))%2==0)) && ((n-a+(a-u)/2)>=p))
    {
        cout << "YES\n";
        for (int i = 0; i<(k-p); i++)
        {
            if (!odd.empty())
            {
                seq[i].push_back(odd.back());
                odd.pop_back();
            }
        }
        for (int i = (k-p); i<k; i++)
        {
            if (!even.empty())
            {
                seq[i].push_back(even.back());
                even.pop_back();
            }
            else
            {
                seq[i].push_back(odd.back());
                odd.pop_back();
                seq[i].push_back(odd.back());
                odd.pop_back();
            }
        }
        for (auto it:odd)
        {
            seq[k-1].push_back(it);
        }
        for (auto it:even)
        {
            seq[k-1].push_back(it);
        }
        for (int i = 0; i<k; i++)
        {
            cout << seq[i].size();
            for (auto it:seq[i])
            {
                cout << ' ' << it;
            }
            cout << '\n';
        }
    }
    else 
    {
        cout << "NO\n";
        return 0;
    }
}

 

이때 팀원들은 C에서 LCA가 나온다는 이유로 손절해버리고, D는 뭔가 어렵게 생겼다면서 일단 넘긴 후 E를 읽어보고 있었다.

뭐 그런가보지, 라고 생각했는데, 팀 전략이 산으로 갔다는 걸 이때는 인지를 못했다.

 

E번 문제가 설명하기 상당히 빡세고, "조금만 더 생각하면 각이 나올 것 같다" 라면서, 팀원들이 다른 거 먼저 보고 있는게 낫겠다고 했다.

 

그리고 일단 무슨 2차원 dp, 3차원 dp 이런 얘기들을 하던데, 보기 싫어졌다.

---

G. Merge Sort

Solution : Gratus907

Code : Gratus907

팀원들이 E번을 보는 사이에 F번을 한번 읽어보고, 일단 뒤 문제가 뭔지 볼 생각으로 G번을 풀기 시작했다. 그런데 생각보다 너무 좋은 관찰이 빠르게 찾아져서 쓱싹했다 ㅇㅁㅇ

 

merge sort가 재귀함수를 이용해서 구현되어 있을 때,

$n$까지의 permutation을 만들어서 mergesort(l, r)이 정확히 $k$ 번 호출되게 하는 문제이다.

 

다음과 같은 함수 $\texttt{reverse_sort(l, r)}$ 를 생각해 보자.

- 만약 구간 [l, r) 이 이미 정렬되지 않은 상태라면, 그대로 둔다. 

- 만약 구간 [l, r) 이 정렬된 상태라면, 가운데 두 원소 arr[mid], arr[mid+1] 을 서로 바꾸고 재귀 호출한다.

 

이 함수는 merge sort를 완전히 거꾸로 돌린 것으로, 멀쩡하게 정렬된 array에 이 함수를 호출하고, 다시 merge sort를 호출해 보면, merge sort의 호출 횟수와 reverse sort의 호출 횟수가 같아야 함을 알 수 있다. 이걸 이용해서, 호출 횟수가 $k$번이 될때까지 재귀하는 식으로 reverse_sort를 만들어 주면 된다. 끝까지 다 호출했는데도 $k$가 남았으면 불가능하고, $k$가 짝수여도 불가능하다. 처음 한번 호출 이후에는 계속 0번 또는 2번 재귀되기 때문.

#include <bits/stdc++.h>
using namespace std;

int arr[101010];
int n, k;

int reverse_sort(int l, int r)
{
    if (k==0)
    {
        return 0;
    }
    else 
    {
        if (l+1 >= r)
        {
            return 0;
        }
        k -= 2;
        int mid = (l+r)/2;
        int tmp = arr[mid];
        arr[mid] = arr[mid-1];
        arr[mid-1] = tmp;
        reverse_sort(l,mid);
        reverse_sort(mid,r);
        return 0;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i<=n; i++)
    {
        arr[i] = i;
    }
    if (k%2==0)
    {
        cout << -1;
        return 0;
    }
    else 
    {
        k--;
        reverse_sort(1, n+1);
    }
    if (k==0)
    {
        for (int i = 1; i<=n; i++)
        {
            cout << arr[i] << ' ';
        }
    }
    else 
    {
        cout << -1;
        return 0;
    }
}

뭔가 이상하게도 둘이서 아직도 dp 테이블 얘기를 하고 있었다. 단순히 dp만 해서 끝나는 문제가 아닌듯 했다.

 

일단 diordhd가 먼저 지금 짜려는 게 없으니 지금까지 얘기한 부분을 구현한다며 컴퓨터를 잡았다.

---

H. Marmots (easy)

Solution : Gratus907

Code : Gratus907

뭔가 E번 구현이 끝없이 늦어지는 와중에, 코딩해야 할 문제의 큐가 점점 쌓이고 있었다. 내가 H번이 매우 쉽게 해결될 수 있음을 알았고, 얼마 되지 않아 Coffeetea가 F번도 대충 풀이를 작성했고, I번도 둘이 같이 잠깐 얘기했는데 대충 어찌어찌 될 것 같다는 식으로 얘기가 나왔다. 그래서 일단 diordhd가 E번 dp 테이블 채우는 부분을 구현해 둔 다음, 내가 한 15분 만에 H번 코딩을 그냥 밀었다.

 

문제가 굉장히 이상한데다, 일단 예제 입력을 한 개도 안 주는 이상한 문제.

숫자 250개가 주어진다. 이것들은 평균이 $P$인 푸아송 분포로부터 뽑은 것이거나, [0, 2P] 까지의 Uniform 분포로부터 뽑은 것이다.

데이터를 보고 어느 분포인지 판정하자.

 

공학수학에서 배운 지식을 이렇게 써 볼 줄은 몰랐다.

푸아송 분포는 다음과 같은 확률 질량 함수를 갖는다. (이건 당연히 주긴 했지만..)

$$f(k) = \frac{P^k}{k!} \cdot e^{-P}$$

특징으로는, 평균과 분산이 모두 $P$이다.

 

균등 분포의 경우, 분산이 평균보다 훨씬 커지게 된다. 구체적으로는 구간 길이의 제곱에 비례하는 분산을 갖는다. 이 경우, 평균은 $P$이고, 분산은 $(2P)^2$ 의 상수배 정도 이므로 (구간 길이 $L$에 대해 $\frac{L^2-1}{12}$) 수 배, 수십 배 내지는 $P$가 커지면 수백 배 차이도 날 수 있다. ($P$ 는 10에서 1000) 

따라서, 250개 숫자에 대해서 평균과 분산을 구해보고, 그 비가 어떤 일정한 값 이상이면 균등, 이하면 푸아송이라고 판정할 수 있다. 넉넉하게 2를 잡았는데, (사실 약간 쫄리긴 했는데, P가 작으면 균등분포에서 차이가 별로 안 나서... 확률이 충분할까 싶었다)

다행히 충분해서 한번에 AC.

#include <bits/stdc++.h>
using namespace std;

int u = 250;
void check()
{
    vector <double> arr;
    for (int i = 0; i<u; i++)
    {
        double x;
        cin >> x;
        arr.push_back(x);
    }
    double tole = 2;
    double sqsum = 0, sum = 0;
    double sqavg = 0;
    double mean = 0, var = 0;
    for (auto it:arr)
    {
        sum += it;
        sqsum += (it*it);
    }
    mean = sum/u;
    sqavg = sqsum / u;
    var = sqavg - mean*mean;
    if (var/mean>tole)
    {
        cout << "uniform\n";
    }
    else 
    {
        cout << "poisson\n";
    }
    return;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int v;
    cin >> v;
    while(v--)
    {
        check();
    }
}

이 시점에서 약간 선택의 기로에 놓였는데, Coffeetea가 일단 먼저 빨리 짤 수 있는 F를 짜겠다고 선언했다. 그래서 바로 F번을 코딩하고, 나랑 Diordhd가 K번을 생각하기 시작했다.

---

K. Police Patrol

Solution : Diordhd, Gratus907

Code : Gratus907

사실 처음에는 뇌피셜로 시작해서, 결국은 대략적으로 증명 하고 냈다.

$x$축 위에 범죄자 $n$명이 뿌려져 있고, 어딘가 한곳에 경찰서를 세운다. 그리고 나서 경찰차를 타고 돌면서 범죄자들을 잡아서 경찰서에 데려다놓는데, 한번에 차에는 $m$명 만 넣을 수 있다. 이동 거리의 최솟값을 구하자.

단, 범죄자가 있는 곳에 경찰서를 세워도 되며, 이경우 그 범죄자는 바로 잡힌다.

관찰을 통해 일단 이미 범죄자가 있는 곳에 세우는 것이 이득임을 알 수 있고, 구체적으로는 잡아야 할 목표들의 좌표의 중간값에 세우는 것이 가장 최선임을 알 수 있다.

귀류법으로 증명 가능한데, 중간값에서 약간 벗어나 보면, 가까워지는 목표물들의 수 * 가까워지는 거리 보다 멀어지는 목표물들의 수 * 멀어지는 목표물들의 거리 가 더 크거나 같다. 이유는 양쪽의 거리는 같은데 숫자가 멀어지는 것이 항상 같거나 많기 때문.

 

그리고 나서, 양쪽 끝을 돌면서 (한쪽 끝으로 갔다가 다시 돌아와서 내려놓고 반대쪽 끝으로 가기) 양쪽 끝에서부터 $m$명 씩을 데려올 수 있다. 이 전략이 최선임은 그리 어렵지 않게 보일 수 있다. (물론 라운드 중에는 믿음으로 코딩하면서 Diordhd가 반례를 생각해보고 있었다)

#include <bits/stdc++.h>
#define int ll
using namespace std;

typedef long long ll;
int n, m;
int arr[1010100];
ll ans = 0;
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i<n; i++)
    {
        cin >> arr[i];
    }
    int pt1 = 0, pt2 = n;
    while(pt1 < pt2)
    {
        ans += (arr[pt2-1]-arr[pt1])*2;
        pt2 -= m;
        pt1 += m;
        if (pt1 >= pt2)
        {
            break;
        }
    }
    cout << ans;
}

정해는 뭔가 dp스러운 거였던거 같은데... 굳이?

 

K번을 먼저 푼 이유는, F번 코딩 중 예제 출력에서부터 문제가 생겨서, F번 디버깅 하는 동안 막간에 K번 코딩을 좀 해보려다가 그대로 쭉 풀었기 때문이다. F번 디버깅이 마침 딱 적절한 시간에 끝나서, 나는 Diordhd랑 I번을 생각하러 가고, Coffeetea가 다시 F번을 잡았다.

---

F. Ordering Pizza

Solution : Coffeetea

Code : Coffeetea

나랑 같이 생각한다고 하긴 했지만, Coffeetea가 풀이를 생각하고 코딩하러 갈 때까지 나는 그게 왜 되는지 이해도 못하고 있었다. 끝없이 볼록함수 그래프를 그리며 헤매고 있었기 때문에 Solution도 1명인 걸로 하자.

$n$ 명의 학생이 각각 먹고 싶은 피자 조각 수와, 각 피자를 먹었을 때 (2종류다) 조각당 얻는 행복이 정해져 있다. 한 판이 $S$조각인 피자를 너무 많이 사지 않으면서 (먹일 수 있는 최소 수만 사면서), 학생들의 행복의 총합을 최대화하자.

 

내가 Ternary Search를 생각하고 이게 정말 볼록함수가 맞는지 생각하며 미궁에 빠진 동안, Coffeetea가 이 문제를 케이스 몇개 나누면 그리디처럼 생각할 수 있다고 주장하고 코딩하기 시작했다. 내가 K번 푸는 동안 디버깅 얼추 해서, 제출하고 (Overflow로 1틀 당한 후) 맞았다.

 

대략적인 풀이는, 먼저 모두 각자 더 선호하는 피자를 준 다음, 모자라고 남는 피자를 확인해서 가장 반발이 적은 사람의 피자를 바꾸는 식으로 진행된다.

#include <bits/stdc++.h>
using namespace std;

long long int piece1, piece2;
long long int utility;

int main(){
    long long int p, s;
    scanf("%lld %lld", &p, &s);
    long long int eat[p], left[p], right[p];
    for (int i = 0 ; i < p ; ++i ) {
        scanf("%lld %lld %lld", &eat[i], &left[i], &right[i]);
        if ( left[i] >= right[i] ) {
            piece1 += eat[i];
            utility += eat[i] * left[i];
        } else {
            piece2 += eat[i];
            utility += eat[i] * right[i];
        }
    }
    long long int left1 = piece1 % s;
    long long int left2 = piece2 % s;
    //printf("%lld %lld\n", left1, left2);
    if ( (s - left1) + (s - left2) >= s ) {

        long long int minusutil1to2 = 0, minusutil2to1 = 0;
        priority_queue< pair<long long int, long long int>, vector<pair<long long int, long long int>> , greater<pair<long long int, long long int>> > pq1to2, pq2to1;

        for ( int i = 0 ; i < p ; ++i ) {
            if ( left[i] >= right[i] ) {
                pq1to2.push(make_pair( left[i] - right[i] , eat[i] ) );
            } else {
                pq2to1.push(make_pair(right[i] - left[i] , eat[i] ) );
            }
        }

        while(left1 > 0 ) {
            long long int temputilitychange = pq1to2.top().first;
            long long int temppiece = pq1to2.top().second;
            pq1to2.pop();
            //printf("qq%lld %lld %lldqq\n", temputilitychange, temppiece, left1);
            
            if ( left1 >= temppiece ) {
                left1 -= temppiece;
                minusutil1to2 += temputilitychange * temppiece;
            } else {
                minusutil1to2 += temputilitychange * left1;
                left1 = 0;
            }

            //printf("%lldppp\n", minusutil1to2);
        }
        while(left2 > 0) {
            long long int temputilitychange = pq2to1.top().first;
            long long int temppiece = pq2to1.top().second;
            pq2to1.pop();
            //printf("qq%lld %lldqq\n", temputilitychange, temppiece);
            
            if ( left2 >= temppiece ) {
                left2 -= temppiece;
                minusutil2to1 += temputilitychange * temppiece;
            } else {
                minusutil2to1 += temputilitychange * left2;
                left2 = 0;
            }
        }
        //printf("%lld %lldaa\n", minusutil1to2, minusutil2to1);
        utility -= min(minusutil1to2, minusutil2to1);


    }

    printf("%lld", utility);
}

바로 내가 I번 잡았다. 

---

I. Chocolate 

Solution : Gratus907, Coffeetea, Diordhd

Code : Gratus907

$a \times b$ 짜리 초콜릿과 $c \times d$ 초콜릿이 있을 때, 둘 중 하나를 골라서 

- 반으로 쪼개거나

- 1/3을 떼낼 수 있다. (자연수 크기 만큼만)

 

두 초콜릿의 크기를 같게 하고, 그 크기를 출력하는 문제.

$ab = 2^{x_1} \cdot 3^{y_1} \cdot K_1$ 이고, $cd = 2^{x_2} \cdot 3^{y_2} \cdot K_2$ 일 때, 2와 3은 위 두 과정들을 통해 임의로 줄일 수 있으므로 $K_1 = K_2$ 가 초콜릿의 크기를 같게 할 수 있는 필요충분조건이다. 

생각해 보면, 일단 둘 중 3이 많은 쪽을 3을 필요한 만큼 줄여 주고, 

그 다음 2가 많은 쪽의 2를 필요한 만큼 줄여 주는 것이 당연히 최적이다. 

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> pii;
pii x, y;
int m;
int s1, s2;
int a1,a2,b1,b2;

void oper_x(int i)
{
    if (i==2)
    {
        if (x.first%2==0)
            x.first/=2;
        else
            x.second/=2;
        a1--;
    }
    else
    {
        if (x.first%3==0)
        {
            x.first/=3;
            x.first*=2;
        }
        else
        {
            x.second/=3;
            x.second*=2;
        }
        b1--;
        a1++;
    }
}

void oper_y(int i)
{
    if (i==2)
    {
        if (y.first%2==0)
            y.first/=2;
        else
            y.second/=2;
        a2--;
    }
    else
    {
        if (y.first%3==0)
        {
            y.first/=3;
            y.first*=2;
        }
        else
        {
            y.second/=3;
            y.second*=2;
        }
        b2--;
        a2++;
    }
}


int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> x.first >> x.second;
    cin >> y.first >> y.second;
    s1 = x.first*x.second;
    s2 = y.first*y.second;
    while(s1%2==0)
    {
        s1/=2;
        a1++;
    }
    while(s1%3==0)
    {
        s1/=3;
        b1++;
    }
    while(s2%2==0)
    {
        s2/=2;
        a2++;
    }
    while(s2%3==0)
    {
        s2/=3;
        b2++;
    }
    if (s1!=s2)
    {
        cout << -1;
        return 0;
    }
    m = b1+b2+abs((a1+b1)-(a2+b2))-2*min(b1,b2);
    if (b1>b2)
        while(b1>b2)
            oper_x(3);
    else
        while(b2>b1)
            oper_y(3);
    if (a1>a2)
        while(a1>a2)
            oper_x(2);
    else
        while(a2>a1)
            oper_y(2);

    cout << m << '\n';
    cout << x.first << ' ' << x.second << '\n';
    cout << y.first << ' ' << y.second << '\n';
}

어렵지 않게 클리어.

---

E. Salazar Slytherin's Locket

Solution : Diordhd, Coffeetea

Code : Diordhd, Coffeetea

라운드 시작 40분 후부터 누군가 붙잡기 시작해서, 마침내 AC를 받을 때까지 무려 3시간이 걸린 문제.

어렵기도 하지만, 코딩할 떄 생각할 게 많은 것도 있고, 우리가 dp를 못 짜는 것까지 겹쳐서... 결국 나는 이게 무슨 문제인지 잘 모른다.

뭔가 $b$진법으로 표현했을 때 모든 각 숫자가 짝수번 나오는 수의 개수를 세는? 그런 문제인 것 같던데, 이 문제에 대한 글은 언젠가 내가 이해를 하고 나면 / 또는 누군가 설명을 해 주면 쓰기로 하자.

 

우선 페어코딩도 경험해 봤고, 두명이 일단 파트 나눠서 코딩하기도 했고, 아무튼 팀워크를 잘 볼 수 있는 문제였다. 

코드 링크 (너무 길어서 링크로 대체)

---

후기 

사실 Whining 할게 별로 없다. 우리 취향에 안맞는 문제가 많았는데도 생각보다 굉장히 잘했다. 연습시간이 7시~11시 였던 것도 있는데도...

 

원래는 Whining 할게 많은 라운드 였는데, E번을 마지막에 어떻게 AC를 받았는지는 잘 모르겠지만 아무튼 200줄을 짜고 적어도 컴퓨터 잡는 시간 기준 80분 (240분 중), 생각 타임 기준 250분 정도는 쓴 거 같은데 (단순히 3명의 시간 * 240분 = 720분 기준으로), 이게 실전에서는 전략을 좀 생각할 필요가 있다.

 

가장 성공적인 것은, 팀원들이 E번에서 고전하는걸 보고 3명 모두가 E번에 달려드는 대신 내가 G, H를 혼자 풀러 갔고, 2명도 계속 E를 붙잡는 대신 어디부터 어디까지 누가 코딩, 어디부터 어디까지 누가 코딩을 정해놓고 빠져나와서 나랑 같이 K, F, I를 풀었다. 굉장히 판단이 안 서는 상황인데, Diordhd가 나한테 "이거 설명하면 엄청 오래 걸린다. 필요하면 너가 읽고, 일단 다른거 풀어" 라고 바로 말해준게 좋은 판단이었던 것으로...

 

실제 대회 중에도, 3명이 동시에 한 문제에 30분 이상을 쓰는 일이 없어야겠다. 가급적 인원은 2:1로 잘 배분되는 편이 좋고, 우리 같은 팀에게 가장 좋은 방법은 2명이 풀던 문제가 풀리면 1명이 코딩하러 가고, 1명이 다른걸 읽거나 문제 파악이 끝났으면 1명이 풀던 문제로 넘어가는 식으로 가야할 것 같다.

 

나는 사실 E번이나 F번은 절대 코딩 못했을 것 같은데, Coffeetea가 내가 못하는 구현을 잘해서 정말 다행인듯.