Little Piplup 6월 2일 팀 연습

Little Piplup의 세 번째 팀 연습

팀연습 기능을 몇번 안써봐서 체크박스가 무슨의미인지 오늘 알았다. 실수로 내 계정만 들어갔다;;;

 

약간의 구현 뇌절이 팀원 전체적으로 있었는데, 그래도 스코어 자체는 그렇게 심각하지는 않았다.

 

ELO의 시스템의 원리 상, 라운드 당시 참가자들의 레이팅 변화를 보면 우리 퍼포먼스가 대략 어느정도인지 알 수 있다. 당시 비슷한 점수를 받은 참가자들 중, 레이팅 변화가 0에 매우 가까운 사람을 찾으면 대략 그 정도가 ELO 시스템이 예측한 우리의 Performance Rating임을 알 수 있다. 물론 실제로는 $\Delta R = 0$ 인 사람을 찾더라도 $\pm$ 10점 정도까진 오차가 있다. (이 값을 계속 트래킹하는 것도 나쁘지 않을 것 같아서, 앞으로는 코포로 팀연습을 돌때는 Tracking 해두려고 한다)

Team performance equivalent to : 2040

문제 번호	A	B	C	D	E
문제 레이팅	800	1500	1600	1800	1900
AC 시간 (+틀린 횟수)	00:01	00:43	00:18 (+1)	02:13 (+1)	01:53 (+2)

B번부터 1500이 나오는건 약간 예상 밖이지만... 사실 문제가 어려운건 아니고, 구현이 귀찮았다. 

---

A. Definite Game

Solution, Code : Gratus907

$n$ 과 $n-1$은 언제나 서로소이므로, $n-1$을 빼주면 항상 1로 만들 수 있다. 딱 하나의 예외가 2인데, 2는 1을 빼 줄 수 없어서 $n = 2$ 일 때는 2를 출력, 그외에는 1을 출력.

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

int main()
{
    int a;
    scanf("%d",&a);
    printf("%d",a==2? 2: 1);
}

---

B. Farewell Party

Solution : Gratus907, Coffeetea, Diordhd

Code : Gratus907

뭔가 모자를 썼다가 벗은다음 다시 쓰는 과정에서 교란순열이 생각나고, 다른 모자 어쩌고 해서 뭔가 더더욱 교란순열이 떠올랐지만 전혀 아니다.

나와 다른 색깔 모자를 쓴 사람이 $k$명임을 각자가 report 해주는데, $k$ 라는 숫자가 $n-k$의 배수번 나오지 않는다면 뭔가 잘못된 것이므로 impossible을 출력, $k$가 $n-k$ 의 $u$배만큼 나온다면 $n-k$ 명씩 끊어서 다른 모자를 주면 된다. 그리디하게 해결 가능.

상당히 구현이 귀찮았는데, 막 벡터를 occurrence에 따라 10만개 잡고 어쩌고 하면서 시간을 꽤 많이 썼다. 내가 코딩을 하는 도중 C번을 팀원들이 순삭해서, C번 코딩하라고 잠깐 컴퓨터를 넘겨줬다. 앉아서 B번 구현할 자신이 없어서(...) 

내가 그리디 구현을 상당히 못한다는건 느끼고 있지만, 구현이 생각을 못따라가는건 다른 팀원들도 마찬가지라 어쩔수가 없었다. 그나마 C번 풀이하는 시간동안 내가 기껏 생각이랍시고 한게 구데기같은 구현인건 약간 :thinking_face: ...

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

int arr[101010];
int occ[101010];
int hat[101010];
int ht = 1;
ll sqs = 0;
vector <int> ks[101010];
int main()
{
    int n; 
    scanf("%d",&n);
    for (int i = 1 ; i<=n; i++)
    {
        int x;
        scanf("%d",&x);
        arr[i] = x;
        occ[x]++;
        sqs += arr[i];
    }
    if (occ[0])
    {
        if (sqs == 0)
        {
            printf("Possible\n");
            for (int i = 0; i<n; i++)
                printf("1 ");
            return 0;
        }
        else 
        {
            printf("Impossible");
            return 0;
        }
    }
    
    for (int i = 1; i<=n; i++)
    {
        if((occ[i]>0) && ((occ[i]%(n-i))!=0))
        {
            printf("Impossible");
            return 0;
        }
        ks[arr[i]].push_back(i);
    }
    for (int i = 1; i<=n; i++)
    {
        int ss = ks[i].size();
        if (ss==0)
            continue;
        int u = n-i;
        for (int j = 0; j<ss; j++)
        {
            hat[ks[i][j]] = ht + j/u;
        }
        ht += ss/u;
    }
    printf("Possible\n");
    for (int kk = 1; kk<=n; kk++)
            printf("%d ",hat[kk]);
    return 0;
}

코드가 문제의 난이도에 비해 상당히 길다. 이럴 필요가 없을 것 같은데...

---

C. Colorful Bricks

Solution : Diordhd, Coffeetea

Code : Coffeetea

내가 B번 코딩하는 사이에 순식간에 팀원들이 C번을 밀었다. 원래는 dp가 정해고 별해로 closed-form 수식이 있는것 같은데, dp문제라는건 아무도 생각하지 못했다(...)

 

$n$개의 칸으로 된 블록을 최대 $m$개의 색깔로 칠할 건데, 색이 바뀌는 지점이 정확히 $k$번만 있어야 한다. 

이 문제를 dp 점화식으로 표현하면 다음과 같이 쓸 수 있다(고 한다).

$i$번째까지의 블록을 $j$번 색깔 변화를 주면서 칠하는 방법의 수를 $f(i, j)$ 라고 할 때,

\[ f(i, j) = f(i-1, j) + f(i-1, j-1)(m-1)\]

초기값을 잘 주고 $f(n,k)$ 를 구하면 된다. 

 

두명 (그리고 나중에 들은 나도) 저런 솔루션은 전혀 생각하지 못했고, 당연히

색깔이 바뀔 $k$번을 먼저 고른 다음, 처음에는 $m$ 색 중 하나, 그다음부터는 $m-1$색 중 하나씩 고를 수 있으니

\[ \binom{n-1}{k} m (m-1)^k \]

이거 구하면 된다고 생각했다. 나는 이 문제 생각 시점에 B 코딩 중이어서, B번 코딩이 끝난 다음 Diordhd에게 브리핑만 들었는데 매우 간단해 보이길래 그냥 바로 D로 넘어가기로 했다.

 

예외 케이스 ($m == 1$) 에 걸려서 한번 틀리고, B 맞은 다음 돌아왔다.  

 

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

int c[2005][2005];       //c[a][b] = a C b

int getc(int a, int b ) {
    if ( c[a][b] == - 1 ) {
        if ( b == 0 ) {
            c[a][b] = 1;
        } else if ( b == 1 ) {
            c[a][b] = a;
        } else if (a == b ) {
            c[a][b] = 1;
        }
        else {
            if ( b > a - b ) c[a][b] = getc(a, a-b);
            c[a][b] = ( (long long int) getc(a-1, b-1) + getc(a-1, b) ) % mod;
        }
    }
    return c[a][b] % mod;
}

int main(){
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);

    for ( int i = 0 ; i <= n ; ++i ) {
        for ( int j = 0 ; j <= n ; ++j ) {
            c[i][j] = -1;
        }
    }

    if ( k == 0 ) {
        printf("%d", m);
    } else if ( m == 1 ) {
        printf("0");
    }else {
        int ret = getc(n-1, k);
        ret = (long long int) ret * m % mod;
        for (int i = 0 ; i < k ; ++i ) {
            ret = (long long int) ret * (m-1) % mod;
        }
        printf("%d", ret);
    }
}

---

D. Maximum Distance

Solution : Gratus907, Diordhd, Coffeetea

Code : Gratus907

문제 설명이 상당히 복잡해서 영어 해석에 꽤 오랜 시간이 걸렸다.

어떤 두 점 $i, j$ 사이의 경로의 길이를 다음과 같이 정의한다.

"경로가 지나는 간선의 가중치 중 최댓값"

이때, 두 점 사이의 거리는 "가장 짧은 경로의 길이" 로 정의한다.

 

Special Vertex가 $k$개 주어지고, 각각에 대해, 다른 special vertex까지의 거리 중 가장 먼 것을 출력한다.

 

우선 문제 풀이에 들어가고 얼마 안되어서 내가 이 문제는 MST로 푸는 거라는 나름의 상당한 확신을 가졌고, Kruskal의 정당성 증명 때처럼 생각하면 주어진 문제의 답은 $k$개 모두 "MST에 추가되는 가장 긴 간선" 을 그냥 찾으면 된다고 주장했고 Kruskal을 짜기 (팀노트에서 베끼기) 시작했다.

결과적으로는 아예 틀리진 않았지만 중요한 생각이 빠진 주장이었는데, special vertex와 무관한 간선을 출력하게 될 수도 있다. 예를 들어, 다음 케이스

이렇게 생긴 그래프에서 special vertex가 2, 3, 4이면 서로 간의 거리는 항상 1이므로 답이 1이지만, MST를 만들다 보면 100짜리 간선이 들어가게 된다.

 

결국은 Kruskal로 MST를 짜면서 special vertex가 몇개 들어와 있는지를 계속 트래킹하다가, 다 들어오면 MST 만들기를 멈춰야 하는데 이 작업이 상당히 어렵게 느껴졌다. 그래서 일단 Coffeetea에게 E번 구현을 넘겨주고 구현을 조금 생각하고 들어가기로 했는데, E번도 WA on test 11이 나면서 상당히 고전했다.

 

결국 두개를 거의 번갈아서 코딩하기 시작했고 (인쇄를 할 수 없는 환경이라서, 대신 듀얼모니터 한쪽에는 코드를 띄워만 놓는 식으로 똑같은 상황을 만들었다) 1시간 정도 번갈아서 코딩하다가 E번을 1시간 53분, D번을 2시간 13분에 맞았다. E번을 짠 후에, 그냥 Kruskal에서 에지를 커팅하겠다는 생각을 포기하고 생각해보니 Prim으로 짜면 트래킹이 간편할 듯 해서 Prim으로 갈아탔다. 혹시나 해서 (아직 매끄럽게 짤 자신은 없기때문에) 어제 급하게 팀노트 초안에다가 MST를 얹어왔는데 그걸 써먹게 될줄은 몰랐다.

#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define mod 998244353;
typedef pair<int, int> pii;

vector<pii> Tree[101010];
bool visit[101010];
priority_queue<pii, vector<pii>, greater<pii>> pq;
int special;
bool is_special[101010];
void add(int i)
{
    visit[i] = true;
    for (auto it:Tree[i])
    {
        //if (!visit[it.second])
            pq.push(it);
    }
    if (is_special[i])
        special--;
}
int maxedge = -1;
int Prim(int start)
{
    int mstlen = 0;
    add(start);
    while(!pq.empty())
    {
        int cur = pq.top().second;
        int we = pq.top().first;
        pq.pop();
        if (visit[cur])
            continue;
        else
        {
            if (special==0)
                return 0;
            mstlen+=we;
            maxedge = max(maxedge,we);
            add(cur);
        }
    }
    return mstlen;
}
int arr[101010];
int main()
{
    int v,e,k;
    scanf("%d %d %d",&v,&e,&k);
    special = k;
    for (int i = 0; i<k; i++)
    {
        scanf("%d",arr+i);
    }
    for (int i = 0; i<k; i++)
    {
        is_special[arr[i]] = true;
    }
    for (int i = 0; i<e; i++)
    {
        int st,ed,we;
        scanf("%d %d %d",&st,&ed,&we);
        Tree[st].push_back({we,ed});
        Tree[ed].push_back({we,st});
    }
    int mstlength = Prim(arr[0]);
    for (int i = 0; i<k; i++)
        printf("%d ",maxedge);
}

---

E. Missing Numbers

Solution : Diordhd, Coffeetea

Code : Coffeetea

어떤 $n$개 짜리 수열의 짝수번째 항들이 주어지고, 홀수번째 항들을 $10^{13}$ 이하의 항들로 채워서 모든 prefix sum이 제곱수가 되게 할 수 있는지를 묻는 문제였다. 설명만 듣고는 상당히 어려울 것 같았는데, 의외로 둘이 굉장히 빠르게 풀이를 찾았다. (그리고 또 코딩이 오래 걸렸다)

 

풀이의 핵심은 두 제곱수 $p$ 와 $q$의 차 $p^2 - q^2$가 $(p+q)(p-q)$ 로 나뉠 수 있음을 이용한다. 특히, 여러 Choice가 있는 경우 최대한 제곱수를 작게 만드는 그리디한 접근이 필요하다.

 

 

최종 결과 배열을 $ans[i]$ 라고 하자.

$i$번째 수에 대해, $\sqrt{arr[i]}$부터 1까지 t를 내려 보면서 $arr[i]$의 가장 큰 약수를 찾는다. 이 수를 $t$ 라고 하자.

만약 $arr[i]/t - t$가 홀수라면 (즉, $arr[i]$ 와 $t$의 패리티가 다르다면) 답이 될 수 없으니 남기고,

이 값을 이용하여 최대한 작은 $m$ 과 $n$을 각각 다음과 같이 구한다.

\[m = \frac{arr[i]/t - t}{2} \]

\[n = \frac{arr[i]/t + t}{2} \]

이제 홀수번째 항 $ans[i-1]$ 을 $m^2 - ans[i-2]$ 로 하면 된다.

이러면 $m^2$가 $ans[i-1]$ 까지의 누적합, $n^2$ 가 $ans[i]$ 까지의 누적합이 될 것이다.

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

long long int soo[100005];
long long int boo[100005];

int main(){
    bool cando = true;
    int n;
    scanf("%d", &n);
    for (int i = 2 ; i <= n ; i += 2 ) {
        scanf("%lld", &soo[i]);
    }
    for (int i = 2 ; i <= n ; i += 2 ) {
        long long int sqlast = sqrt(boo[i-2]);

        long long int now = soo[i];
        long long int sqnow = sqrt(now);
        int t;
        for ( t = sqnow ; t > 0 ; --t ) {
            if ( now % t == 0 ) {
                long long int op = now/t - t;
                if ( op % 2 == 1 ) continue;
                long long int m = (now/t - t) / 2;
                long long int n2 = (now/t + t) / 2;
                if ( m <= sqlast ) continue;
                else {
                    //printf("q %d q %d q\n", m, n2);
                    //즉, 현재 수는 n^2 - m^2
                    //이거 전까지는 m^2였다는 거지
                    soo[i-1] = (long long int)m * m - boo[i-2];
                    boo[i-1] = (long long int)m * m;
                    boo[i] = (long long int)n2 * n2;
                    break;
                }
            }
        }
        if (t == 0) {
            cando = false;
            break;
        }
    }


    if ( cando ) {
        printf("Yes\n");
        for ( int i = 1 ; i <= n ; ++i ) {
            printf("%lld ", soo[i]);
        }
    } else {
        printf("No");
    }
}

사실 나는 이 솔루션이 완전히 이해가 가질 않는데, 일단 그리디하게 도는게 뭔가 그럴듯하다는 생각은 든다. 

---

Review

Performance Based Rating : 2040

 

라운드 자체는 굉장히 재미있었다. 거의 끝까지 뭔가를 했기도 하고, 세명 비중도 그렇게 나쁘지는 않았다. (다만 약간 비중측면에서 보완해야 할 점은 있다는 느낌을 받았다.) 가장 기분나쁜 라운드는 한 1시간 정도 만에 풀수있는 문제를 다 풀고 다음 문제가 갑자기 2500짜리 팍 나와서 어어어 하면서 1시간 30분이 날아가는 이런 라운드들이 제일 기분나쁜데 (그래서 CF도 5문제짜리 라운드는 정말 뛰기 싫어진다. 같은 이유로 지금은 ARC를 참가하고싶은 의욕이 굉장히 떨어진다.) 팀으로는 2000짜리정도 문제도 풀 수 있기 때문에 그런 일이 잘 없다. 

 

 

여전히 team(A, B, C) > max(A, B, C) 가 잘 성립하는 팀인 것은 맞는듯하다. 객관적으로 동일 레이팅으로 3명 추린 팀 중에는 나쁘지 않으니, 개인 기량에 집중하자 라는 메타기도 하고. 

팀연습을 통해서는 항상 굉장히 많이 배운다. 알고리즘을 말하면서 생각하려면 조금더 정제된 생각을 해야 하기도 하고, 이 문제를 다른 사람은 어떻게 접근하는지 (특히 나랑 같이 문제를 풀 사람은 어떤 생각을 하는지) 는 내 생각을 다듬는데 큰 도움이 된다고 생각한다.

 

이번 연습에서 가장 문제가 된 부분은 여전히 구현력이다. Coffeetea가 그나마 낫긴 하지만, 여전히 생각하는 그대로를 구현에 옮기지 못해서 생기는 문제점이 상당하기도 하고, 무엇보다 Diordhd가 아예 키보드를 안 잡은 채로 2시간 30분이 지나고 라운드가 종료되었다는 것은 우리처럼 3명 모두가 Solve/Code를 지향하는 팀 (사실은, 한명이 코딩을 전담할 만큼 코딩실력이 좋은것도 아니기도 하지만, 세명 모두가 저렇게 하는 것이 가장 라운드를 즐길 수 있는 방법이라는 매우 중요한 측면이 있다.) 에서는 그닥 좋은 현상은 아니라고 생각한다.

 

얼마전에 고려대학교의 hongjun7님 (월파도 나갔던 팀인 것으로 알고 있다) 이 Startlink live에서 발표하셨던 "Teamwork in Programming Contests" 라는 자료를 우연히 접하게 되었다. 그 자료에서 본 내용 중에는 문제풀이 스케줄링의 중요성이 있었는데, 우리 팀은 아직 사실 스케줄링에 대한 경험이 없다. 현재로서는 리저널을 돌기에는 개인기량이 부족해서 Codeforces Round로 연습을 하고 있지만, 이 연습의 가장 큰 문제점은 "몇번 문제가 쉬운 문제이며, 우리가 손댈 수 있는 문제가 어디까지인지" 를 미리 알고 시작한다는 점이다. 차라리 문제를 Random Shuffle해주는 기능이 있었으면 좋겠다는 생각이 드는데... 가장 큰 차이로, ICPC나 UCPC같은 대회들은 "몇번 문제가 쉬운지" 를 미리 알려주지 않으며, 스코어보드를 보면서 알아야 한다. 그러나 상위권 팀들의 스코어보드는 그들이 생각하는 난이도와 우리에게 느껴지는 라운드가 다르니 위험하고 (우리가 모르는 웰노운 알고리즘을 쓰는 문제는, 최상위팀이 10분컷하더라도 우리 팀에게 늪이 될 수도 있다!), 장기적인 관점에서는 선구안을 기를 필요가 있다.

 

오늘 나온 얘기 중 하나는 Codeforces에서 boj쪽에서 열심히 활동하셨던 분들이 모인 road to grandmaster 연습세션이 1700~2400 문제 12문제를 랜덤순서로 4시간 라운드를 마련해 주니, 시간이 딱 맞지 않더라도 이걸 버츄얼로 돌면 어떻겠냐는 얘기가 나왔다. 사실 오늘도 나는 저걸 하자고 제안할 생각도 있었는데, 시험기간에 4시간짜리 연습은 조금 부담이 있어서 가볍게 할 수 있는걸로 준비한 것이긴 해서...

 

아무튼, 결국 요약하면

• 구현력이 부족하니 팀원들 모두 약간의 랭작이 필요하다. 특히 CF 기준 1400~1500 문제는 우리 팀이 "상당히 빠르게 솔루션을 생각하지만 구현에서 말리는" 케이스가 꽤 있는데, 이걸 없애는게 가장 중요하다고 본다.
• 그래프 공부좀 하자! MST정도는 안보고 쓱싹 짤수있어야 한다고 생각한다.
• 장기적으로는 선구안을 기르는 연습도 분명히 필요하다.

이런 정도를 많이 느꼈다.