Codeforces Global Round 16 복기

이번에는 Codeforces Global Round, 문제가 A, B, C, D1, D2, E, F, G, H로 그냥 Codeforces Round보다 문제가 더 많다.

문제수가 늘어나서 그런지 초반 문제들의 난이도가 훨씬 쉽다고 체감됐다. D2문제의 난이도가 기존 Round들의 C 문제 정도 난이도로 느껴졌다.

A, B, C, D1까지 다 한번 제출로 통과했을 정도의 난이도. 보통 B나 C에서 예외처리를 빼먹거나 테스트 케이스에서만 정답이 나오는 코드를 제출해서 두세 번씩은 제출하는데 이번에는 한 번에 통과했다. (Div. 3 난이도랑 비슷한 것 같기도 하다)

D1을 풀었으니 D2는 조금만 손보면 풀 수 있을 것 같아서 끝까지 D2를 붙잡고 있다가 못풀었다... D2까지만 풀었으면 만족스러웠을 텐데 아쉽다.

https://codeforces.com/contest/1566/problem/D2

Problem - D2 - Codeforces

먼저 D1 문제를 기준으로 문제를 설명하면, 영화관에서 n명의 관객과 n개의 좌석이 가로로 한 줄 있을 때 관객이 순차적으로 왼쪽에서 오른쪽으로 좌석에 입장한다. 각 관객은 sight level이 있어 sight level이 낮은 관객이 높은 관객보다 오른쪽에 있으면 안 된다. 입장할 때 이미 자리에 있는 관객을 한 명 지날 때마다 불편함(inconvenience)이 1씩 증가한다.

이 때, 불편함이 가장 낮게 입장하는 경우의 불편함을 출력하는 문제.

D1은 각 입력마다 이미 들어간 관객 중 sight level이 작은 관객의 수만큼 불편함이 증가하는 것을 쉽게 알 수 있다. 보통 D1, D2 문제에서 입력 크기만 차이나고 시간 복잡도만 달라지는 경우가 많아 D1은 O(n^2), D2는 O(nlogn)인 문제일 거라 생각해서 각 입력마다 이전 입력을 하나씩 확인하는 O(n^2)로 제출하니 통과했다.

D2는 n개의 행과 m개의 열로 되어있을 때 똑같이 불편함을 구하면 된다. 하지만 차이점은 입장을 할 때 자신이 들어가는 행의 관객만을 지나가기 때문에 자신보다 sight level이 낮은 관객이 먼저 입장했더라도 그 관객과 다른 행에 들어간다면 그 관객을 지나치지 않는다.

그래서 내가 D1에 사용한 방법을 그대로 사용할 수 없다.

D1을 푸는 동안 막연하게 D2는 이진 탐색으로 O(nlogn)으로 만들면 되겠다 생각했었는데 아예 다른 접근법이 필요해 당황했었다. 입력값을 정렬한 결과를 좌석의 처음부터 끝까지 나열하면 최종 결과와 같다는 사실을 활용해야 된다는 것인데 입력과 최종 결과 사이의 연관관계를 사용해 답을 어떻게 구해야 할지 감이 오지 않았다.

    cin >> n >> m;
    vector<pair<int, int>> a(n * m);
    for (int i = 0; i < n * m; i++) {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a.begin(), a.end());

이 고민이 솔루션의 처음 코드에서 명료하게 해결해서 이걸 왜 생각 못했지 후회했다.

sort함수에 pair를 사용하면 first를 기준으로 정렬을 해주기 때문에 first에 sight level를 넣고 second에 입력 index를 넣고 정렬을 하면 최종 결과와 입력이 결합된 자료구조가 만들어진다.

하지만 아직 완벽한 상태가 아니다. sort 함수에서 first가 같은 경우 second를 사용해 정렬하기 때문에 first가 같은 경우 index가 낮은 순으로 정렬되어 있다. 오른쪽부터 순차적으로 앉아야 서로 지나치지 않아도 되는데 전부 지나치는 경우가 되어버린다. 

for (int i = 0; i < n * m; i++) {
	a[i].second = -a[i].second;
}
    
int res = 0;
for (int i = 0; i < n; i++) {
	sort(a.begin() + (m * i), a.begin() + (m * i + m));
    for (int j = 0; j < m; j++) {
        for (int k = 0; k < j; k++) {
            if (a[i * m + k].second > a[i * m + j].second) res++;
        }
    }
}

그래서 solution에서는 index를 음수로 바꾸어 행별로 정렬하는 방법을 사용한다. 

이제 완전하게 최종 결과를 알게 되었으니 불편함만 구하면 된다. 이제는 D1에서 사용했던 방법과 비슷하게 진행할 수 있다. 대신 sight level을 비교하는 것이 아니라 index를 비교해서 자신보다 왼쪽에 존재하고 index를 음수로 바꿨으니 index가 더 큰 경우에 불편함을 증가시킨다.

난이도가 다른 라운드보다 쉬웠긴 했지만 A, B, C를 다 풀어서 기분은 좋았던 라운드. A밖에 못 푸는 충격적인 라운드들이 있어 자신감이 떨어지던 찰나에 쉬었다 가는 느낌이다. 

그리고 6 라운드 참가가 끝나 점수를 1200점 정도로 배치받았다. 가장 낮은 newbie등급을 간신히 벗어난 점수...

이번 연도 안에 퍼플을 가겠다고 목표를 정했지만 지금 실력으로는 올해 안으로는 어렵지 않을까 생각이 든다.

랭커들의 점수 그래프를 궁금해서 살펴봤는데 대부분 오랫동안 꾸준하게 알고리즘을 해온 사람들인걸 보니 나도 알고리즘을 길게 보고 꾸준히 하다 보면 재미도 있고 프로그래머로써 실력도 꾸준히 향상할 수 있지 않을까 생각이 들었다.