Posted 2021-02-18Algorithm / APSS / CodeForces15 minutes read (About 2194 words)0 visits

01. CodeForces Round #703 (Div.2) 풀이 & 후기

대회 소감

첫 번째 CodeForces 대회였다. 당분간 초점은 무조건 적응이다. 나는 알고리즘의 굉장한 실력자가 결코 아니기 때문에 쉬운 A, B번 문제를 얼마나 빨리 푸는가가 생각보다 점수와 등수를 많이 가른다. 허나 본인은 여기에 삽질까지 추가로 해버리고 있기 때문에.. 어서 타임어택의 CP에 적응해야 한다.

다음의 사항들에 중점적으로 적응하도록 하자.

C 개발환경의 문제 (형변환, 오버플로우, 함수 용법)
문제 똑바로 읽고 이해하기
- 대부분의 A는 쉬운 수학인데, 확실하게 풀고 코드로 옮기자
시간 복잡도 계산해보고 코드로 넘어가기
TLE가 떴다면, 아예 다른 접근으로 생각하기

풀이

A (Shifting Stacks)

문제 보기

A번 문제 풀이 + 본인의 코드

stack의 이동이 i → i+1 로의 커지는 방향으로만 가능했다는 것을 읽지 못하여 try를 2번이나 소모하였다. 깨달은 후에 바로 해결한 쉬운 수학문제

교훈

문제를 꼼꼼히 읽자

'Round #703 - A.cpp : AC'

#include <cstdio>
using namespace std;
#ifdef __APPLE__
#include "dbg.h"
#else
#define dbg(...)
#endif

int main() {
   int t;
   scanf("%d", &t);
   while(t--) {
       int n;
       bool flag = false;
       long long sum = 0;
       scanf("%d", &n);
       long long h[102];
       for(int i = 0; i < n; i++) {
           scanf("%lld", &h[i]);
       }

       for(int i = 0; i < n-1; i++) {
           h[i+1] += h[i] - i;
           if(h[i+1] < i+1) {
               flag = true;
               break;
           }
       }

       if(flag) printf("NO\n");
       else printf("YES\n");
   }
}

B (Eastern Exhibition)

문제 보기

B번 문제 풀이 + 본인의 코드

삽질하느라 A번이 늦었던 것 치고 굉장히 빨리 B번을 해결하였다. $|x_1 - x_2| + |y_1 - y_2|$에서 앞 두 항이 완벽하게 독립이라는 사실을 바로 캐치하였고, 이어서 홀수일 때는 답이 항상 1이라는 것을 알아냈다. 이처럼 쉬운 수학 문제의 경우에는 규칙 찾기가 굉장히 중요하다는 교훈을 얻었다. 처음에 문제를 보자마자 쫄아서 “빠르게 테스트”하는 방법을 고민하였는데, 주어진 숫자 범위에서는 당연히 TLE가 뜰 수밖에 없다. 이를 빨리 깨닫고 넘어갔으면 더 빠르게 풀었을 것이라고 생각한다. 심지어 변수 선언을 마지막에 실수로 long long으로 해주지 않아 한 번의 try를 날렸다.

교훈

어려워 보이는 (앞 번호) 문제라면 규칙 찾기를 시도해 볼 것.
변수형 선언 꼼꼼히 하기 (애매하면 그냥 long long으로 두기)

'Round #703 - B.cpp : AC'

#include <cstdio>
using namespace std;
#ifdef __APPLE__
#include "dbg.h"
#else
#define dbg(...)
#endif

#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        int n;
        scanf("%d", &n);
        vector<long long> x;
        vector<long long> y;
        for(int i = 0; i < n; i++) {
            long long a, b;
            scanf("%lld %lld", &a, &b);
            x.push_back(a);
            y.push_back(b);
        }
        if(n%2 == 1) {
            printf("1\n");
            continue;
        }
        dbg(x);
        dbg(y);
        sort(x.begin(), x.end());
        sort(y.begin(), y.end());
        long long a = x[n/2] - x[n/2 - 1] + 1;
        long long b = y[n/2] - y[n/2 - 1] + 1;
        printf("%lld\n", a*b);
    }
}

C2 (Guessing the Greatest - hard version)

문제 보기

C번 문제 풀이 + 본인의 코드

흔하지는 않은 interactive 문제를 인생 첫 코드포스 대회에서 만나 놀랐다. 나중에 확인해 보니 대회 전에 공개된 round 소개에 나와 있었다. 본인은 하나도 준비를 안한 채 만나서 당황도 했고, 무엇보다도 문제 이해 + 구현에 꽤 많은 시간이 들었다.

사실 문제를 보자마자 아이디어는 굉장히 빠르게 떠올랐다 - 이진탐색!
어떤 배열에서 두 번째로 큰 수의 위치를 얻는다. 이후, 가장 큰 수가 그 수 기준으로 왼쪽에 있는지 오른쪽에 있는지 판별할 수 있다 (왼쪽 혹은 오른쪽 구간에서 query 한 번을 사용) 이런 이진탐색 스러운 느낌을 살려서 가장 큰 수를 찾으면 되는데…

위 아이디어를 살려 코드를 제출하였지만, 3번 pretest에서 발생하는 TLE를 해결하지 못한 채 대회가 종료되었다. 끝나고 곰곰히 생각해 본 결과, 이진탐색의 느낌을 살리는 것이 아니라 “정말 이진탐색과 똑같이” 해도 상관 없음을 확인하였다. 기존까지는 두 번째로 큰 수를 포함하는 범위로 나누었는데, 사실 이렇게 하면 worst case에서는 최악으로 시간복잡도가 $O(n)$이 되므로, TLE가 뜰 확률이 높다. 그냥 이진탐색을 돌리면 되었다. (조금 더 자세히 말하자면, 맨 처음에만 두 번째로 큰 수를 포함하는 범위로 나눠주면 된다) ~~왜 이걸 찾지 못했을까~~

이 아이디어로는 C2(hard version)이 통과되며, C2보다 시간 제약이 더 널럴한 C1은 당연히 통과된다.

교훈

TLE가 발생하면 알고리즘 자체를 다시 생각해보자

'Round #703 Upsolving - C.cpp : AC'

#include <cstdio>
using namespace std;
#ifdef __APPLE__
#include "dbg.h"
#else
#define dbg(...)
#endif
#include <iostream>

int ask(int start, int end) {
    if(start >= end) return -1;
    printf("? %d %d\n", start, end);
    fflush(stdout);
    int response;
    cin >> response;
    return response;
}

int main() {
    int n;
    scanf("%d", &n);
    int secondMax = ask(1, n);
    if(secondMax == 1 || ask(1, secondMax) != secondMax) {
        int left = secondMax, right = n;
        while(right - left > 1) {
            int middle = (left + right) / 2;
            if (ask(secondMax, middle) == secondMax) {
                right = middle;
            } else {
                left = middle;
            }
        }
        printf("! %d\n", right);
    } else {
        int left = 1, right = secondMax;
        while(right - left > 1) {
            int middle = (left + right) / 2;
            if (ask(middle, secondMax) == secondMax) {
                left = middle;
            } else {
                right = middle;
            }
        }
        printf("! %d\n", left);
    }
}

D (Max Median)

문제 보기

D번 문제 풀이 + 본인의 코드

업솔빙 할 당시에도 문제 감을 전혀 잡지를 못해서 Tutorial을 참고하여 힌트를 얻었다.
전반적인 아이디어 틀은 Binary Search, 좀 더 상세히 말하자면 Parametric Search 였다. 어떠한 x에 대하여 이 값이 median으로 가능한지 확인해 보는 방향이다. 이는 첫 번째 힌트인 “모든 값이 -1 또는 1일 때를 생각해 보라” 에서 추리할 수 있다. 이 특수한 경우에서는,’부분 수열의 합이 0 이상이다 = -1의 개수보다 1의 개수가 많다’를 의미한다.
이 힌트는 왜 갑자기 등장했을까. 어떠한 x에 대하여, x보다 작거나 같은 값들을 -1로, x보다 큰 값들을 1로 변경한다. 그러면, 부분 수열의 합이 0 이상이 된다는 것은 “x 이상인 값이 median이 될 수 있음”을 보장해 준다! 여기까지가 문제풀이의 가장 큰 핵심이 된다. 부분 수열의 합은 Prefix Sum으로 구한다.
허나, 한 가지 아이디어가 더 필요하다. 아직 변수 k를 고려하지 않았다! 그러나 각 탐색 작업에 $O(k)$의 시간복잡도를 투자하여 부분 배열을 검사하는 것은 TLE로 이끈다. 필자는 Gravekper 로부터 아이디어를 받았는데, prefix sum들의 최솟값을 저장하는 배열을 하나 더 선언하는 것이다. 이렇게 하면 $O(k)$를 들여 검사를 하지 않고 preSum[i]와 minSum[i-k] 의 대소 비교 한 번을 통해 가능성 여부를 파악할 수 있다.

Upsolving 하고 나니 꽤나 많은 힌트들을 필요로 했고, 아이디어도 굉장히 많이 요구되었던 것 같다. 대충 아직 나의 실력보단 높은 난이도 란 뜻이다. D번의 Upsolving은 실전의 도움보다는 지적 호기심이 더 맞겠다 ㅎㅎ

'Round #703 Upsolving - D.cpp : AC'

#include <cstdio>
using namespace std;
#ifdef __APPLE__
#include "dbg.h"
#else
#define dbg(...)
#endif
 
#include <cstring>
#include <algorithm>
#define MAX_N 200000
 
int n, k;
int arr[MAX_N+5];
 
bool check_X(int x) {
    // check if x is possible for answer
    int brr[MAX_N+5], preSum[MAX_N+5], minSum[MAX_N+5];
    memset(brr, 0, sizeof(brr));
    memset(preSum, 0, sizeof(preSum));
    memset(minSum, 0, sizeof(minSum));
 
    if(arr[1] < x) brr[1] = -1;
    else brr[1] = 1;
 
    preSum[1] = brr[1];
    minSum[1] = min(preSum[1], minSum[0]);
 
    for(int i = 2; i <= n; i++) {
        // set values of preSum and minSum
        if(arr[i] < x) brr[i] = -1;
        else brr[i] = 1;
        preSum[i] = preSum[i-1] + brr[i];
        minSum[i] = min(minSum[i-1], preSum[i]);
 
        if(i >= k && preSum[i] > minSum[i-k])
            return true;
    }
    return false;
}
 
int main() {
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
    }
 
    // binary search
    int l = 1;
    int r = n;
    int m, ans = arr[1];
    while(l <= r) {
        m = (l+r)/2;
        if(check_X(m)) {
            ans = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    printf("%d\n", ans);
}