Codeforces Round #563 (Div.2) 후기/풀이

Little Piplup 팀원들이 어쩌다보니 다 같이 라운드를 돌게 되었고, 거기에 우리 학교에서 약간 실력 비슷한 다른 팀 3명도 같이 뛰게 되고... 전반적으로 친구들이 많이 같이 뛴 라운드.

 

그래서인지 뭔가 처음부터 마음이 조금 급했던 것 같다는 생각이 든다.

 

Rating Change : -5 (1889 -> 1884)

마지막 11점이 이렇게 어렵다...!

 

문제 풀이

---

A. Ehab Fails to Be Thanos

그냥 sort 해보고, 앞 반의 합이랑 뒤에 반의 합이 같으면 불가능, 다르면 그대로 출력해 버리면 되는, Div2 A 치고도 간단한 문제인데 정수 나눗셈이라는 뇌절로 Hack당했다. 게다가 Lock을 걸어놔서 뭐가 틀렸는지도 20초만에 알았지만 못고쳐서 굉장히 기분이 나쁘고, 더 기분이 나쁜 사실은 저게 아니었으면 퍼플을 무난히 달았을 것이라는 사실이다.

앞으로는 절대 Lock 안걸고 문제만 풀 생각이다. 어차피 남의 코드 읽어서 Hack을 성공한 적도 없고.

 

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

int arr[2010];
int main()
{
    int n;
    ll sum = 0, newsum = 0;
    scanf("%d",&n);
    for (int i = 0; i<n*2; i++)
    {
        scanf("%d",arr+i);
        sum += arr[i];
    }
    sort(arr,arr+n*2);
    for (int i=0; i<n; i++)
        newsum+=arr[i];
    if (newsum*2!=sum)
        for (int i = 0; i<n*2; i++)
            printf("%d ",arr[i]);
    else
        printf("-1");
}

 

---

B. Ehab is an Odd Person

홀수와 짝수 중 하나에만 몰려있는 (즉, 홀수만 있거나 짝수만 있는) 배열이라면 아무것도 할 수 없다.

홀수와 짝수가 각각 하나 이상 있다면, 홀수 하나를 적당히 들고 이리저리 돌아다니면서 짝수들을 sort하고, 그위에 홀수들을 sort해서 전체 배열을 sort할 수 있다.

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

int arr[101010];
int odd, even;
int main()
{
    int n;
    scanf("%d",&n);
    for (int i = 0; i<n; i++)
    {
        scanf("%d",arr+i);
        if (arr[i]%2)
            odd++;
        else
            even++;
    }
    if (odd==n || even == n)
        for (int i = 0; i<n; i++)
            printf("%d ",arr[i]);
    else
    {
        sort(arr,arr+n);
        for (int i = 0; i<n; i++)
            printf("%d ",arr[i]);
    }
}

---

C. Ehab and a Special Coloring Problem

$(i, j)$ 가 서로소인 경우 $a[i] \neq a[j]$ 만 성립하면 된다.

서로소라는 말에서 바로 힌트를 얻으면 되는데, 어떤 수 $k$에 대해 $k$의 가장 작은 소인수를 $u$라고 하자. 이때, $u$가 몇번째 소수인지만 출력해 주면, 항상 주어진 조건을 만족할 수 있음을 쉽게 보일 수 있다.

두 수가 서로소이기 위해서는 소인수를 공유하지 않아야 하므로, $u$의 값이 자명하게 다르다.

 

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

const int BIGNUM = 101010;
int pcount = 1;
int p[BIGNUM];
bool is_composite[BIGNUM];
void sieve()
{
    for (int i = 2; i <= BIGNUM; i++)
    {
        if (!is_composite[i])
        {
            p[pcount++] = i;
            for (int j = i * 2; j <= BIGNUM; j += i)
                is_composite[j] = true;
        }
    }
}

int least_prime_div(int k)
{
    for (int i = 1; i<=pcount; i++)
        if (k%p[i]==0)
            return i;
}

int main()
{
    int n;
    scanf("%d",&n);
    sieve();
    for (int i = 2; i<=n; i++)
        printf("%d ",least_prime_div(i));
}

---

D. Ehab and the Expected XOR Problem

BOJ 13504 (XOR Sums) 를 풀어본 경험이 도움이 되었다.

어떤 배열에서, subsegment $(a, b]$ 의 XOR 값은, prefix xor 배열 $p$ 에 대하여 $p[b] \oplus p[a-1]$이다.

 

먼저, 어떤 prefix 배열이 정해지면, 그에 맞는 적절한 원래 배열이 항상 정해진다는 것을 기억하자. 

즉, $arr[i] = prefix[i] \oplus prefix[i-1]$ 이 항상 올바른 arr의 값을 준다는 것이다.

 

문제의 요구 조건은, 모든 subsegment의 XOR값이 0이나 $x$가 되지 않기만 하면 된다. 즉, 모든 prefix xor값들을 저장한 배열 p에 대하여,

p에서 두 수를 뽑아서 xor값이 0이 되거나 (즉, 두 수가 같거나), $x$가 되는 경우만 없으면 된다는 것이다.

 

다음 두 가지로 경우를 나누어 보자.

 

1) 문제의 $x$가 범위 안에 없을 때

모든 수가 distinct하기만 하면 항상 valid한 prefix이다. $1, 2, 3 \dots 2^n-1$ 을 prefix로 갖는 배열을 구하면 끝.

 

2) 문제의 $x$가 범위 안에 있을 때 

우리가 사용할 수 있는 수는 총 $2^n - 1$ 개이다. 그러나, 하나라도 값이 $x$이면 안 될 것이므로 실제로는 $2^n -2$개밖에 사용할 수 없음을 쉽게 보일 수 있다.

 

이제, 이중에 적당히 $a, b, c \dots$ 를 뽑는데, $a \oplus x$, $b \oplus x$ 가 절대 들어가지 않게만 뽑자.

즉, 만약에 우리가 1~7까지의 수 중 $x = 5$ 를 피하고 싶다면, 

1을 뽑으면, 1 xor 5 = 4이므로 4는 피한다.

2를 뽑지 못할 이유가 없으므로 뽑으면, 2 xor 5 = 7이므로 7을 피한다.

3도 마킹되지 않았으므로 3을 뽑고 3 xor 5 = 6을 피한다.

뽑는 수와 피하는 수가 정확히 $\frac{2^n-2}{2}$ 개 씩인데, 그 이유는 XOR이 다음을 만족하기 때문이다.

  \[ a \oplus b = a \oplus c \Rightarrow b = c\]

양변에 $b$ 를 xor해보면 왜인지 알 수 있다.

 

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

int n, x;
int L = 0;
int xor_prefix[1001000];
bool marked[1001000];
int main()
{
    scanf("%d %d",&n,&x);
    int u = (1<<n);
    if (x >= (1<<n))
    {
        L = (1<<n)-1;
        for (int i = 1; i<u; i++)
            xor_prefix[i] = i;
        printf("%d\n",L);
        for (int i = 1; i<u; i++)
            printf("%d ",xor_prefix[i] xor xor_prefix[i-1]);
    }
    else
    {
        L = ((1<<n)-2)/2;
        if (L==0)
        {
            printf("0");
            return 0;
        }
        int cur = 1;
        marked[x] = true;
        for (int i = 1; i<u; i++)
        {
            if (!marked[i])
            {
                xor_prefix[cur] = i;
                marked[i xor x] = true;
                cur++;
            }
        }
        printf("%d\n",L);
        for (int i = 1; i<=L; i++)
            printf("%d ",xor_prefix[i] xor xor_prefix[i-1]);
    }

}

---

후기 (Whining)

사실 이제 슬슬 시험기간이라 코포를 뛸 것인지 꽤 고민을 했는데, 퍼플까지 11점 남기도 했고, 친구들이 다 같이 뛰기로 해서 일단 뛰는것 까지는 별로 문제가 없었다.

그런데 뭔가 계속 마음이 급했는지 별 이상한 실수를 하면서 (배열 2천개 잡아야 하는데 1000개인줄 알고, 문제 B번에서 배열 10만개로 바뀌었는데 A번에서 쓴 2천개 그대로 내고...) 틀릴 이유가 없는 문제를 계속 한번씩 미스냈고, 결국 A번에서 Hack당했다. (멘탈 관리가 조금 필요하다는 생각이 든다)

40분 만에 ABCD를 푼 다음, EF를 보니 솔브 수가 매우 적었다. 대략 "아 또 1시간 20분동안 멍때리다 끝나겠구나" 라는 생각이 들어서 (난이도를 아는 것의 최대 문제다), 일단 솔루션을 전부 락한다음 핵이라도 돌아볼까 하고 봤는데, 언어를 처음 배울때 PS하면서 배우다보니 내 코딩 스타일에만 손이 익어서인지 나는 다른 사람 코드 읽고 분석하는걸 상당히 못한다. 핵에서 아무것도 얻지 못하고 그냥 E번이나 보러 가자 하고 봤더니 Lock을 건게 화근;; 앞으로는 절대 락 안걸고 그냥 문제만 풀 생각이다. 당분간 Hack을 생각해야 할 이유가 별로 없기도 하고.

 

ELO 레이팅에 실력이 대략적으로 수렴했다는 생각이 든다. 문제는 요즘 Codeforce에 익숙해지다보면 복잡한 알고리즘 문제보다 그리디, 구현 계열 문제들만 많이 풀게 되는데, 그래프 문제 같은걸 연습할 필요가 있다. 어쨌든 목표는 UCPC/ICPC 등 대회니까. Combined Round들을 보면 D~E에서 적당한 그래프 문제 잘만 나오던데, 요새 왜인지 연속 몇라운드째 Construction, 비트연산, Greedy 만 미친듯이 나오고 있다.