Little Piplup 5월 19일 팀연습

Little Piplup의 두 번째 팀 연습

문제셋은 Codeforces Round 500 (Based on EJOI) 로, 지금 우리는 일단 Div.2 수준 문제들을 확실히 푸는게 필요하기 때문에 당분간은 이정도 느낌의 셋으로 연습하는게 좋을 것 같다. 조금 실력 쌓고나면 ARC랑, 쉬운 리저널부터 돌아야지.

 

3명 팀이 대충 1900정도 되는 퍼플 1명이랑 비슷해 보인다.

레이팅 자체는 내가 1870이긴 한데, 최소 150점은 거품인게 내 눈에도 보이기 때문에(...) 1700정도 레이팅 문제부터 고전하기 시작한다.

 

문제 번호	A	B	C	D	E
문제 레이팅	800	1200	1500	1900	2000
AC 시간(+틀린 횟수)	00:22 (+2)	00:36 (+1)	00:42 (+1)	01:13	02:20

누가 보면 A 레이팅이 최소 1600은 되는줄 알것 같다.

---

A. Piles With Stones

Solution, Code : Coffeetea

Coffeetea가 뇌절하고 결자해지했다. 

 

A번은 지난번과 똑같이, 시작할 때 컴퓨터를 잡은 사람이 맞추고 시작하기로 했다. 사실 Div.2 라운드 같은 경우에는 B번이 별로 어렵지 않다면, A번을 푼 사람은 B번에 관여하지 않고 바로 C번을 보는 방법이 우리 퍼포먼스에는 더 맞다고 생각한다. 이미 B번 솔루션 스케치 까지는 끝냈을 거라고 믿고...

 

돌을 탑 $i$번에서 $j$번으로 한번에 하나씩 옮기거나, 하나를 아예 빼는 행동을 무한히 반복할 수 있을 때 탑의 집합 $A$를 $B$로 만들 수 있느냐 하는 문제이다.

총 개수가 $A \geq B$ 이면 무조건 가능하고, 아니면 안 되는 단순한 문제로,

 

원래대로라면 3분만에 풀고 넘어갔어야 하지만...

영어 해석의 실수로 "돌 탑 두 개를 서로 바꿀 수 있고, 하나의 탑을 아예 0으로 만들 수 있다" 라고 이해했는데, 하필 예제 테캐 3개가 그렇게 해석하고서도 답이 달라지지 않는 테캐들이 주어져서 해석이 틀리다는걸 한참 뒤에 알았다. (영어 해석이 중요한 이슈가 될 수 있다는 것도 덕분에 체감했다) 그렇게 22분이 날아갔고, 팀연습하면서 최대의 난점인 '컴퓨터 병목 현상' 을 경험했다. 이 시점에 이미 B 풀이를 다 준비하고, C 풀이도 거의 90% 이상 생각해 놨었기 때문에.

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

int main(){
    int n;
    scanf("%d", &n);
    int temp;
    int first = 0, second = 0;
    for ( int i = 0 ; i < n ; ++i ) {
        scanf("%d", &temp);
        first += temp;
    }
    for ( int i = 0 ; i < n ; ++i ) {
        scanf("%d", &temp);
        second += temp;
    }
    if (first >= second ) printf("Yes");
    else printf("No");
}

---

B. And

Solution : Diordhd, Gratus907

Code : Gratus907

두 번 이상의 And는 전혀 의미가 없고, 답은 무조건 -1, 0, 1, 2 중 하나라는 것을 파악하면 그냥 열심히 해보면 풀 수 있다. 어차피 $(A \& B) \& B = A \& B$ 이기 때문.

 

구현이 상당히 귀찮을 것 같았다 (Occurence를 카운팅해서 저장하고, 실제 배열 값이랑 and하고...) 그리고 솔루션을 생각해낸 상황에서 A번이 틀리고 있었기 때문에, 일단 C번을 보기로 했다.

 

나중에 생각한 건데, A번에 무슨 문제가 있길래 15분 시점에서 AC가 나오지 않았는지를 이 시점에 파악했어야 했다.

코드는 실제로는 C번을 먼저 제출했다. (C번이 더 간단하다고 생각했기 때문) 그런데 C번 풀이에 약간 잘못 생각한 점이 있어서, 다시 B번으로 돌아와 맞추고 (그나마도 실수해서 한번 틀렸다) C번을 풀었다.

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

int n,x;
int arr[101010];
int occ[101010];
int andocc[101010];
int main()
{
    scanf("%d %d",&n,&x);
    for (int i = 0; i<n; i++)
    {
        int tmp;
        scanf("%d",&tmp);
        arr[i] = tmp;
        occ[tmp]++;
    }
    for (int i = 0; i<101010; i++)
    {
        if (occ[i]>=2)
        {
            printf("0");
            return 0;
        }
    }
    for (int i = 0; i<n; i++)
    {
        if ((arr[i] & x)!=arr[i])
        {
            if (occ[arr[i]&x])
            {
                printf("1");
                return 0;
            }
        }
    }
    for (int i = 0; i<n; i++)
        andocc[arr[i]&x]++;
    for (int i = 0; i<101010; i++)
    {
        if (andocc[i]>=2)
        {
            printf("2");
            return 0;
        }
    }
    printf("-1");
    return 0;
}

---

C. Photo of The Sky

Solution : Diordhd, Gratus907

Code : Diordhd

$\mathbb{R}^2$ 공간 상의 점들이 많이 주어지고, 이들을 모두 포함하는 가장 작은 직사각형의 넓이를 구하는 문제.

Diordhd가 처음 풀이를 제시했는데, 일단 sort한 다음, $2n$개의 점으로 구성된 array 상에서,

\[ (arr[2n-1] - arr[n])(arr[n-1]-arr[0]) \]

이렇게 답이 나올 것임을 보였다. 듣고보니 맞는것 같은데다 솔루션이 너무 간단하길래 B번보다도 먼저 코딩을 해봤다가 틀렸는데, Diordhd가 다시 저 풀이에 반례가 있음 (많은 좌표들이 같은 숫자라면, 그것들을 이용해서 점들을 한 직선 위에 싹 올릴 수 있다) 을 보이고 다시 코딩해서 (몇줄 추가하고 고친 거지만) 냈다.

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

long long ans1 = 0;
long long ans2 = 0;
long long arr[202020];
int main()
{
    long long n;
    scanf("%lld",&n);
    for (int i = 0; i<2*n; i++)
        scanf("%lld",arr+i);
    sort(arr,arr+2*n);
    long long temp=1000000001;
    for(int i=1; i<n; i++)
        temp=min(temp,arr[i+n-1]-arr[i]);
    ans1 = (arr[2*n-1]-arr[n])*(arr[n-1]-arr[0]);
    ans2 = (arr[2*n-1]-arr[0])*temp;
    printf("%lld",min(ans1,ans2));
}

---

D. Chemical Table

Solution : Diordhd, Coffeetea, Gratus907

Code : Coffeetea

이번 라운드 최고의 문제라고 생각한다. 

$1 \leq x \leq m$, $1 \leq y \leq n$ 을 만족하는 $(x, y)$ 들이 주어진다.

그리고, 좌표평면상에 직사각형을 그어서, 만약 그 중 세 꼭짓점을 이미 가지고 있다면, 나머지 한 꼭짓점을 얻을 수 있다. 이때, 최소 몇 개의 점을 추가로 가지고 시작해야 $m \times n$개의 점을 모두 저 방법으로 얻을 수 있는지를 묻는 문제이다.

 

사실 처음에 거의 감을 못 잡고 있었다. $m, n$ 이 각각 20만이라서 총 칸이 400억 개인 데다가, 처음에 갖고 시작하는 점은 최대 20만 개인데, 처음 가지고 있는 점들을 이용해서 재귀적으로 가능한 점들을 세는 것도 불가능하고...

 

Diordhd가 솔루션을 깔끔하게 제시했는데,

가로줄을 $1$부터 $m$까지의 노드로, 세로줄들을 $m+1$부터 $m+n$ 까지의 노드로 보자.

이때, 점 $(x, y)$ 는, $x$번에서 $y$ 번으로 가는 간선이 있다는 뜻이다.

(예를 들어, $(3,2)$ 는 3번에서 $m+2$번으로 간다)

그러면, 적당히 연결된 그래프가 있으면 그 위의 모든 점들을 반드시 얻을 수 있음을 보일 수 있다. 

 

따라서, 먼저 저렇게 40만개의 정점과 최대 20만개의 간선이 있는 그래프를 그린 다음, 현재 그래프에서 연결 요소의 개수를 세고, 각 연결 요소에서 하나씩만 이어 주면 되니까 현재 연결 요소의 개수 - 1 개의 간선이 추가로 필요하다.

 

우리중에 그래프 코드는 Coffeetea가 제일 빠르고 정확하게 짜기도 하고, 상대적으로 구현 경험이 적은 Diordhd가 솔루션을 생각했는데 내가 꽤 오랜 시간동안 벙쪄있었기 때문에 그대로 Coffeetea가 다시 컴퓨터를 잡았다. 이번에 SNUPS Intro Study 그래프 섹션 준비를 하면서 몇 번 더 짜 봐서인지, 확실히 빠르게 AC를 받았다.

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

vector<int> road[400005];
bool done[400005];

void dfs(int s) {
    int size = road[s].size();
    for ( int i = 0 ; i < size ; ++i ) {
        int temp = road[s][i];
        if ( !done[temp] ) {
            done[temp] = true;
            dfs(temp);
        }
    }
}

int main() {
    int n, m, p;
    scanf("%d %d %d", &n, &m, &p);
    while(p--) {
        int a, b;
        scanf("%d %d", &a, &b);
        road[a].push_back(n + b);
        road[n+b].push_back(a);
    }
    int soo = 0;
    for ( int i = 1 ; i <= n+m ; ++i ) {
        if ( !done[i] ) {
            ++soo;
            done[i] = true;
            dfs(i);
        }
    }
    printf("%d", soo - 1);
}

---

E. Hills

Solution : Gratus907, Diordhd, Coffeetea

Code : Gratus907

$n$개의 수가 주어진다. 이때, 어떤 수가 local maximum 이기 위해서는 좌우에 있는 수들보다 Strictly 커야 한다. 

1의 시간을 소모해서, 아무거나 하나 잡고 숫자를 1 줄일 수 있다.

이때, $k$ 개의 local maximum을 얻고자 하는데, 이 때의 최소 시간을 구해야 한다.

또한, $k$는 1부터 $\frac{n}{2}$ 까지의 모든 값에 대해서 구해야 한다.

 

대략 dp문제인 것은 감이 잡히는데, prefix에 대해 dp를 쓰기에 매우 귀찮은 요소가 있다. local maximum인지를 판정하기 위해서는 앞과 뒤의 원소를 모두 줄여야 해서, 이것을 처리하기가 상당히 까다롭다.

 

먼저, dp[i][j] 를 잡아서 풀어 보려고 했다. 이때 $i$는 prefix, $j$ 는 지금까지 진행하면서 챙긴 local maximum들의 개수.

그런데 이렇게 하면 각각의 항들을 채우기 위해 다시 전체를 한번 돌아보면서 찾아야 하고, 결국은 $n^2$ 개의 항들을 $\mathcal{O}(n)$ 시간에 채우는 게 되어 $\mathcal{O}(n^3)$ 시간에 해결하는 셈이 된다. $n$ 이 1000이면 상수가 작을 것이라고 믿음을 갖고 내보기라도 했을 텐데, 5000이라 절대 못 비빈다.

 

여기까지는 대체로 생각이 비슷하게 왔고, 내가 $[k]$ 를 도입해서 풀면 된다는 생각을 했다. dp[i][j][k]에서, $k$는 0 또는 1로, 0은 "여기에는 짓지 않고", 1은 "여기에 지어서" $i$번 까지 $j$ 개의 local maximum들을 얻는 최소 시간을 의미한다고 하자. 그러면, local maximum이 연속할 수 없으므로, $k = 1$ 일 때의 정보는 $i+2$ 번째 줄을 업데이트하는 데 쓸 수 있고, $k = 0$ 일 때의 정보는 $i+1$번째와 $i+2$번째 업데이트에 모두 쓸 수 있다.

이렇게 하면, 항은 총 $2n^2$ 개이고, 각각은 상수 시간에 채운 셈이 되어 $\mathcal{O}(n^2)$ 시간에 문제를 해결할 수 있다. 

라운드가 끝나고 댓글을 보니 더 간단한 솔루션이라며 제시된 답안이 내 코드랑 거의 같았다. 

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

const int INF = (int)2e9+(int)1e8;
int n;
int dp[5020][5020][2];
int arr[5020];

int reducetime (int p, int v)
{
    if (arr[p]<=v)
        return 0;
    else
        return arr[p]-v;
}

int main()
{
    scanf("%d",&n);
    for (int i = 1; i<=n; i++)
        scanf("%d",arr+i);
    for (int i = 0; i<5020; i++)
        for (int j = 0; j<5020; j++)
            for (int k = 0; k<2; k++)
                dp[i][j][k] = 2100000000;
    dp[1][0][0] = 0;
    dp[1][1][1] = 0;
    for (int i = 1; i<=n; i++)
    {
        for (int j = 0; j<=(n/2 + (n%2)); j++)
        {
            for (int k = 0; k<2; k++)
            {
                int val = dp[i][j][k];
                if (k==0)
                {
	                dp[i+1][j][0] = min(dp[i+1][j][0],val);
                    dp[i+1][j+1][1] = min(dp[i+1][j+1][1],val+reducetime(i,arr[i+1]-1));                
                }
                else
                {
                    dp[i+2][j+1][1] = min(dp[i+2][j+1][1],val+reducetime(i+1,min(arr[i],arr[i+2])-1));
                    dp[i+1][j][0] = min(dp[i+1][j][0],val+reducetime(i+1,arr[i]-1));
                }
            }
        }
    }
    for (int i = 1; i<=(n/2 + (n%2)); i++)
        printf("%d ",min(dp[n][i][0],dp[n][i][1]));
}

---

전체적으로 결과만 놓고 봤을 때는 상당히 선전했다고 본다 (1900, 2000 문제는 사실 우리 지금 레이팅에 비해 300~400점 가까이 높은데, 같이 생각하니 확실히 차이가 조금 느껴진다). 

A번에서 얻은 약간의 교훈 (쉬운 문제여도 침착하게 천천히 읽어야 한다) 이랑, D, E에서의 발상 (특히 2차원 배열에 대한 정보를 행에서 열로 가는 그래프로 생각하는 문제는 처음 접했다) 등에서도 배운 게 많은 것도 있고... 확실히 팀원들 사이에 유형별로 실력이 약간 갈리는 것은 장점이긴 한 것 같기도 하다.

 

신기하게, F번 풀이가 상당히 간단했다. 그리디하게 약간의 작은 케이스들만 처리해 주면 풀리는 문제였고, 내가 E번을 코딩하는동안 Coffeetea가 F번 풀이를 다 생각해 놨다. 15분 정도만 더 있었으면 사실 F번 코딩도 가능했던 상황인데, 쉬운 ABC번에서 코딩 시간을 상당히 많이 잡아먹은 것이 조금 아쉽게 느껴진다.