Codeforces Round #695 (Div. 2)

Codeforces Round #695 (Div. 2)

Codeforces Round #695 (Div. 2)

 

Codeforces Round #695 (Div. 2)에 대한 해설입니다.

 

 * 이 글은 code-review 항목의 포스트입니다. code-review 항목에 대해 자세히 알아보고 싶다면, 클릭!

 * 문항 원문은 아래 주소에서 확인 가능합니다. Codeforces Round #695 (Div. 2)

 - codeforces.com/contest/1467 [ 바로 가기 ]

 

[2021.01.09] 초판 발행

 

 Codeforce Round #695 (Div. 2)에 대한 후기입니다. 2번 문항에서 시간을 많이 잡아먹었네요. 대회가 끝난 후에 출제진이 'Thank you all for participating! My apologies for misjudging the difficulty of B.'라는 말에서 위안을.

 

[A번] Wizard of Orz

 

[문제 및 풀이]

 

 $n$개의 수로 이루어진 수열이 있다. 이 수열은 초기에는 모두 0이었다가, 1초가 지날 때마다 $'0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3,...'$과 같은 식으로 수가 커진다. 특정 시점에 특정한 항을 선택하고, 다음과 같은 동작을 한다.

 

 1. 그 수를 멈추게 한다.

 2. 1초가 지난 후에 그 수와 인접한 항의 수도 멈추게 된다.

 

 이 동작을 해서 수열의 모든 수가 멈추게 되면, 그 수를 나열해서 수를 만든다. 문제는 n이 주어졌을 때, 최종적으로 나오는 수의 크기가 가장 커지도록 하는 '특정 시점에 특정한 항'을 구하는 것이다.

 

 예제를 보고 가장 먼저 드는 생각은 다음과 같은 수열이다.

 

 n = 1 : 9

 n = 2 : 98

 n = 3 : 987

 n = 4 : 9876

 n = 5 : 98765

 

 그 다음에 과연 저 수열이 항상 가능할까 생각이 든다. 항상 가능하다. 마지막 수를 해당 수를 선택하면 된다. 예컨대, $n = 5$일 때는 마지막 항이 $5$일 때 멈추면 된다.

 

 여기서 생각이 멈추면 Wrong answer를 받는다. 여기서 한 발짝 더 생각해보면 다음과 같은 것이 가능하다.

 

 n = 1 : 9

 n = 2 : 98

 n = 3 : 989

 n = 4 : 9890

 n = 5 : 98901

 

 그렇다. $n$이 $2$ 이상일 때에는 왼쪽에서 두 번째 항을 $8$로 끝나게 하면, $'989'$로 수열이 시작되어서 가장 큰 수를 구하게 된다.

 

[구현]

 $n = 1$인 경우는 그냥 $9$를 출력한다. $n = 2$인 경우는 $98$을 출력한 다음에 $901234 ... $와 같은 문자열을 덧붙여서 출력하면 된다.

 

[예시 답안]

 

#include <stdio.h>
 
int N;
char Ans[250000];
 
void process() {
    int i, u;
 
    scanf("%d", &N);
 
    if (N == 1) {
        printf("9\n");
        return;
    }
    
    printf("98");
    N -= 2;
 
    for (i = 0, u = 9; i < N; i++, u++, u%=10) Ans[i] = u + '0';
    Ans[i] = 0;
 
    printf("%s\n", Ans);
}
 
int main() {
    int T;
 
    scanf("%d", &T);
    while (T--) process();
 
    return 0;
}
 

 

[B번] Hills And Valleys

 

[문제 및 풀이]

 

 $n$ 개의 수로 이루어진 수열이 있다. 인접한 두 수 모두보다 큰 항을 언덕(hill)이라고 하고, 인접한 두 소 모두보다 작은 항을 계곡(valley)이라고 하자. 만약 수열의 한 수를 바꾸었을 때, 언덕에 해당하는 항과 계곡에 해당하는 항의 수를 최소화하는 것이 문제이다.

 

 일단, 이 문제도 모든 수를 바꾸어가면서 확인을 한다면 당연히 풀리지만 n 제한에 걸려서 불가능하다. n 제한을 보고 많은 계산을 요하지 않은 방법이 있을 것이라는 생각을 할 수 있다.

 

 이 문제 풀이는 언덕과 계곡의 정의에서 인접한 항에 대해서 '이상/이하'가 아니라 '미만/초과'라는 점에 주목하는 데에 주목한 데에서 시작한다. 만약 어떤 수를 인접한 항 중에 하나로 바꾸면 그 항은 더 이상 언덕이나 계곡이 아닌 상태가 된다. 나아가, 그 인접한 항도 언덕이나 계곡이었다면 그 항 역시 더 이상 언덕이나 계곡이 아닌 상태가 된다.

 

 그리고 수 하나를 바꾸었을 때, 나타나는 효과가 그 항과 그 인접한 두 항만 해당한다. 그렇기 때문에 어떤 항을 바꾸었을 때의 효과는 그 항과 그 항과 인접한 항만 확인하면 된다. 그래서 한 항을 바꾸어가면서 인접한 항이 어떻게 영향을 받는지만 확인하면 된다.

 

[구현]

 입력받은 수열에서 언덕과 계곡의 수(Ans)를 확인한다. 그리고 각 항을 왼쪽으로 인접한 항과 오른쪽으로 인접한 항 각각으로 바꾸어 본다. 그리고 바꾼 후에 그 세 개의 항의 원래 '언덕과 계곡의 수'(Ori)와 항을 바꾸어서 측정한 '언덕과 계곡의 수'(Val)를 비교한다. 이 차이(Cnt)가 가장 큰 항을 구하고, 최종적으로는 초기에 측정한 Ans에서 Cnt를 빼서 출력한다.

 

<유의 사항>

 

 인접한 항을 확인하기 때문에, for문이 기본적으로 $1$ 이상, $(N-1)$ 미만으로 설정하였다. 하지만 '인접한 항(d[i+u])'에 인접한 '인접한 항의 인접한 항(d[i+u-1], d[i+u+1])'은 범위를 넘어서기 때문에, 이 범위를 유의할 필요가 있다.

 

[예시 답안]

 

#include <stdio.h>
#define Max 350000
 
int N, Ans, Cnt;
int d[Max], v[Max];
 
void process() {
    int i, u, t, Ori, Val;
 
    scanf("%d", &N);
    for (i = 0; i < N; i++) scanf("%d", &d[i]);
 
    v[0] = v[N - 1] = 0, Ans = Cnt = 0;
    for (i = 1; i < N - 1; i++) {
        if (d[i] > d[i - 1] && d[i] > d[i + 1]) v[i] = 1, Ans++;
        else if (d[i] < d[i - 1] && d[i] < d[i + 1]) v[i] = 1, Ans++;
        else v[i] = 0;
    }
 
    for (i = 1; i < N - 1; i++) {
        t = d[i];
        Ori = v[i - 1] + v[i] + v[i + 1];
 
        d[i] = d[i - 1], Val = 0;
        for (u = -1; u <= 1; u++) {
            if (i + u - 1 < 0 || i + u + 1 >= N) continue;
            else if (d[i + u] > d[i + u - 1] && d[i + u] > d[i + u + 1]) Val++;
            else if (d[i + u] < d[i + u - 1] && d[i + u] < d[i + u + 1]) Val++;
        }
        Cnt = (Cnt > Ori - Val) ? Cnt : Ori - Val;
 
        d[i] = d[i + 1], Val = 0;
        for (u = -1; u <= 1; u++) {
            if (i + u - 1 < 0 || i + u + 1 >= N) continue;
            else if (d[i + u] > d[i + u - 1] && d[i + u] > d[i + u + 1]) Val++;
            else if (d[i + u] < d[i + u - 1] && d[i + u] < d[i + u + 1]) Val++;
        }
        Cnt = (Cnt > Ori - Val) ? Cnt : Ori - Val;
 
        d[i] = t;
    }
 
    printf("%d\n", Ans - Cnt);
}
 
int main() {
    int T;
 
    scanf("%d", &T);
    while (T--) process();
 
    return 0;
}
 

 

[C번] (작성 전)

 

[예시 답안]

 

[D번] (작성 전)

 

[예시 답안]

 

[E번] (작성 전)

 

[예시 답안]