Codeforces Round #708 (Div. 2) 업솔빙

링크

codeforces.com/contest/1497

Dashboard - Codeforces Round #708 (Div. 2) - Codeforces

 

이번 대회는 중간에 서버가 터져서 unrated 되었다.

망했었는데 너무 다행이다..

이제부터 참가한 라운드를 업솔빙하기로 했다. Problem Set 기준 난이도가 2000 이하인 문제까지는 다시 풀어보려고 한다.

 

A번: 제출시간 00:11

풀이 자체는 문제 해석을 끝내자마자 떠올렸다. 각 원소를 오름차순으로 중복되지 않게 한 번씩 출력한 뒤, 나머지는 뒤에 마음대로 출력하면 된다.

근데 내가 unique() 함수를 잘못 알고 있어 구현이 좀 오래 걸렸다.

보통 벡터에서 중복된 원소를 제거할 때 

v.erase(unique(v.begin(), v.end()), v.end());

이런 식으로 쓰기 때문에 당연히 unique()만 사용하면 앞쪽에 원소들을 중복되지 않게 몰아주고, 나머지를 뒤에 넣어준다고 생각을 했었는데, 그게 아니라 중복되지 않는 원소 하나씩만 앞쪽에 있는 게 보장되며 나머지 원소에 대해선 딱히 명세되지 않은 함수였다.

이건 실수가 아니라 실력이다ㅜㅜ.. 습관처럼 쓰는 함수들도 좀 더 자세히 알아봐야겠다는 생각이 들었다.

 

B번: 제출시간 01:08

각 수를 $m$으로 나눈 나머지로 치환하고, $1$ ↔ ($m-1$), $2$ ↔ ($m-2$), ... 방식으로 개수를 잘 비교하여 답을 도출하면 된다.

 

이 시기에 서버가 터져버렸다. 대회 시작 4x분경 제출을 했고, 그 코드가 틀린 코드였다는 걸 대회 시작 1시간이 넘어서 알게 되었다. 코드 포스 사이트 앞에 m1, m2, m3를 붙여 접속해서 풀라는 공지가 떴었는데 나는 그 공지를 보기도 전에 502, 504 에러만 줄창 떠서 미러 사이트에서 문제를 풀 수 있다는 걸 전혀 모르고 있었다. 친구가 미러 사이트 주소를 주긴 했지만 문제를 볼 수 있는 사이트라고 생각했지 실제 진행 중인 대회를 풀 수 있는 사이트라고는 생각을 못해서 들어가 보지도 않았었다..

 

아무튼 이 시점에서 아 이건 unrated 되겠다 싶어서 마음을 놓고 천천히 뒷 문제들을 봤다.

물론 중간 공지에 나온 "These sites work enough well. Currently, we don't see reasons to make the round unrated." 이 문구를 보고 극대노했다가 unrated 공지 보고 다시 화를 가라 앉힌 건 비밀이다. ^0^

 

================================================

 

C1번

처음엔 수식을 적절히 변형하여 경우의 수를 컷팅하고 남은 범위에서 브루트 포스를 돌리는 게 아닐까 하고 접근했다.

아니었다.. 그냥 어느 정도 브루트 포스로 찍어보고 규칙만 찾으면 되는 문제였다.

내가 찾은 규칙은 다음과 같다.

 

1) $n$이 홀수일 때

답은 1, $\dfrac{n}{2}, \dfrac{n}{2}$이다.

2) $n$이 2의 거듭제곱 꼴일 때

답은 $\dfrac{n}{2}, \dfrac{n}{4}, \dfrac{n}{4}$ 이다.

3) $n$이 그 외의 짝수일 때

$n$을 나눴을 때 $n$을 홀수로 만드는 $2^k$를 $x$라 하면,

답은 $x, \dfrac{n-x}{2}, \dfrac{n-x}{2}$이다.

 

C2번

C1번에서 모든 수에 대해 $k=3$인 경우 정답이 존재함을 보장해주었기 때문에 쉽게 풀 수 있다.

$n, k$가 주어졌을 때 $a_{k}$를 1로 잡아보자.

$LCM(a_{1}, a_{2}, ..., a_{k-1}, 1) = LCM(a_{1}, a_{2}, ..., a_{k-1})$

이므로, 연쇄적으로 $k-3$개의 수는 모두 1로 잡을 수 있고, 문제에서 주어진 $n, k$에 대해 $n = n-(k-3), k = 3$으로 생각하고 C1번의 코드를 그대로 사용할 수 있게된다.

 

C번 문제에서는 constructive한 문제를 풀 때 직접 찍어보고 규칙을 찾아보는 것도 꽤 괜찮은 방법이라는걸 배웠다. 

 

E1번

이런 저런 생각을 해보다 결국 어떤 수의 소인수 중, 개수가 홀수인 것만 처리해주면 된다고 생각했다. 같은 소인수를 2개씩 곱한 수는 오롯이 제곱수이므로 개수가 짝수이면 그 소인수가 없다고 생각하고, 홀수이면 소인수가 하나인 것으로 처리했다.

 

이후 그리디하게 보면서 현재 수가 앞에 나온 적 있으면 그 수끼리의 곱은 완전제곱수이므로 그곳부터 새로운 세그먼트를 만들어주면 된다.

 

처음에 소인수분해를 일반적인 방법으로 처리했더니 TLE를 받았다.

방법을 찾아보니 에라토스테네스의 체를 이용해 더 빠르게 소인수 분해를 할 수 있는 방법이 있었다.

이 방식은 당연히 까먹을 것 같아 여기 올려둬야겠다.

int isPrime[NUM_MAX];
void initPrime() {
    for (int i = 0; i < NUM_MAX + 1; i++) isPrime[i] = i;
    int sq = (int) sqrt(NUM_MAX) + 1;
    for (ll i = 2; i < sq + 1; i++) {
        if (isPrime[i] != i) continue;
        for (ll j = i * i; j < NUM_MAX; j += i) {
            if (isPrime[j] == j) isPrime[j] = i;
        }
    }
 
}
 
vi factorization(ll x) {
    vi factors;
    while (x > 1) {
        factors.push_back(isPrime[x]);
        x /= isPrime[x];
    }
    return factors;
}

 

이번 라운드에선 배운게 정말 많았다.

점수가 대폭 깎였어도 감사히 받아들였을텐데 unrated라 더 괜찮았던 라운드였다 ㅎㅎ