2022 1차 선발고사 후기

어제 1시부터 6시까지 1차 선발고사를 봤다. 올해 역시 코로나로 인해 온라인으로 진행되었기 때문에 12시 반부터 줌에서 대기하면서 신분증 검사 등등을 했다.

문제는 언제나처럼 1번부터 읽으면서 부분점수 견적내고 그랬다. 1, 2번은 문제도 좀 꼼꼼히 읽어야 됐고 좀 힘들어보였는데 3, 4번은 문제 소재가 친숙해서 되게 쉽게 읽혔고 비교적 쉽게 느꼈졌다. 특히 4번은 koistudy에 있는 '날다람쥐'(로그인해야 보인다) 문제와 제목도 같고 스토리도 비슷해서 가장 쉽게 느껴졌다. 사실 국대는 거의 포기한 상태라서 의욕도 별로 없고 요즘 아파서 피곤하기도 해서 1, 2번 읽고 살짝 졸았는데 4번 읽자마자 눈이 번쩍 떠졌다.
쨌든 4번을 만점 받아야겠다고 생각했다.

---

원래의 날다람쥐 문제를 정확히 기억하고 있던 건 아니라서 원래 문제와의 차이점이 이 문제는 모든 나무(=기둥)를 지나가야 한다는 제한이 있는 것뿐인 줄 알았다. 선발고사가 끝나고 확인해보니 다른점이 꽤 많았다. 가장 큰 차이는 나무를 올라갈 때 드는 비용이 나무마다 다르다는 것이었다. 그리고 구 날다람쥐는 이동 가능한 나무의 쌍이 주어지는데, 이 문제는 그런 거 없다. 근데 어차피 모든 나무를 왼쪽에서부터 지나야되므로 바로 다음 나무와만 이동 가능하다고 생각해도 된다. 또 다른 차이점으로는 내려오는 데에는 비용이 들지 않는다는 점과, 맨 마지막 나무에서 도착해야 하는 지점이 입력으로 주어진다는 것이었다.

구 날다람쥐 문제는 여러번 풀어봤었지만 풀이는 그냥 꼭대기로 간다는 거랑 DP밖에 기억이 안났다. 사실 제대로 기억하고 있는건지도 잘 모르겠다. 그치만 저때의 난 구 날다람쥐 문제와의 차이가 딱 '모든 나무 지나기'밖에 없는 아주 유사한 문제라고 생각하고 있었기 때문에 당장 기억나는 풀이에서 확장을 시도했다.
문제를 읽자마자 생각할 수 있는 가장 기본적인 DP는 $O(H(나무의 높이)^2*N(나무의 개수))$정도의 풀이이지만 H가 10억까지 나오기 때문에 너무 부담스러웠다. 그래서 줄여야 된다고 계속 생각하다보니 뭔가 부담스러워서 뇌가 안 굴러가는 느낌이었다. 나무마다 가중치가 다르다는 점에서 감으로 CHT를 사용해야겠다는 의도를 갖고는 있었으나 H를 빼고 생각하자니 풀이가 상상이 안돼서 한참 뇌절을 했다. 그래도 방향성을 갖고 있어서 다행이었던게 결국 문제를 억지로 CHT에 끼워맞추면서 풀었기 때문이다;;ㅋ

내가 생각한 풀이를 구체적으로 써보려고 한다. 그냥 오랜만에 선발고사에서 100점 맞은 문제라 신났다.
내가 머리가 막 좋은것도 아니고, 선발고사때의 생각의 흐름을 따라가면서 살짝 정리 얹어서 설명하는거라 좀 빙빙 돌아가는 느낌이 있다.

어떤 나무의 특정 지점으로 도착하는 방법은
1. 바로 이전 나무에서 적절한 위치에서 날아온 뒤, 가만히 있거나 필요한 만큼 내려오는 것
2. 어찌저찌 도착한 이 나무의 바로 아래 지점에서 W[i](i번째 나무에서 1만큼 올라올 때 드는 비용)만큼의 비용으로 한 칸 올라와 목표 지점에 도착
이렇게 두가지로 생각할 수 있다.

태블릿 갖고 싶다
대충 이런 느낌이다.
(나무 사이의 거리와 나무의 높이가 모두 정수이기 때문에 실수 단위가 아닌 정수 단위로 움직여도 답에 영향이 없다.)

저걸 일일히 구현하면 N*H^2내지는 머리를 살짝 쓰면 N*H정도로 풀 수 있다. 하지만 느리다.
그래서 1번 경로를 하나하나의 간선으로 보지 않고 구간으로 처리해주기로 했다.

(아마 여기서 필요한 위치만 계산하는 방식으로 했으면 N^2에 비례하는 풀이가 나올 것 같다. 그치만 그때의 나는 100점만 생각하느라 안중에도 없었다. 좋은건 아니다..)
그러면 내려오는 데는 비용이 들지 않으므로 이 구간 내에서는 도달비용이 아래로 갈수록 단조감소하는 형태가 될 것이다.

그래프로 나타내 보았다. 직관적으로 보이도록 축을 바꿨다. x가 종속변수, y가 독립변수라고 생각하는게 옳다.

그럼 이제 2번 경로의 출생?에 대해 좀 집중해보자.
2번 경로, 즉 한 칸 아래에서 W[i]의 비용으로 올라오는 방법에서의 '한 칸 아래'에는 어떻게 도착했을까? 얘 역시 바로 아랫지점에서 올라왔든가 전 나무에서 날아왔든가 어쨌든 최소 비용으로 도착했을거다.
그럼 1번 경로를 사용하다가 갑자기 2번 경로를 사용했다면 왜 2번 경로를 사용한걸까?
이전의 어떤 나무에서 한 칸 올라오는 것보다 지금 나무에서 한 칸 올라오는게 비용이 적었거나 높이의 한계로 전 나무에서 더이상 올라갈 수 없었기 때문에 2번 경로를 사용한 것이다.
조금 일반적인 경우인 전자의 경우를 구체적으로 표현하면 현재 나무와 바로 전 나무(x번째 나무와 x-1번째 나무)의 거리를 d라고 하고, D[i][j]를 i번째 나무의 높이 j인 지점에 도달하는 최소 비용이라고 하면 x번째 나무의 높이 y에 도착하려 할 때 $D[x - 1][y + d] - D[x - 1][y + d - 1] > W[x]$였기 때문에 2번 경로를 사용한 것이었다.

(더 자세한 설명은 더보기)

---

1번 경로를 이용한 후 2번 경로를 이용했다는 말은

x-1번째 나무 -> x번째 나무의 높이 y-1 지점(1번 경로 이용) -> x번째 나무의 높이 y 지점(2번 경로 이용)

이렇게 왔다는 거다.

 

이 가정에 의해 $D[k][j - 1] = D[x - 1][y - 1 + d]$

$D[x - 1][y + d] > D[x - 1][y + d - 1] + W[x]$

∴ $D[x - 1][y + d] - D[x - 1][y + d - 1] > W[x]$

---

이렇게 보니 도달 비용의 그래프를 여러 선분으로 표현할 수 있겠다는 생각이 든다.
$D[x - 1][y + d] - D[x - 1][y + d - 1] > W[x]$에서 양변을 y값의 변화량인 1로 나누어주면 마치 좌변은 x-1번 나무의 도달비용 그래프에서의 y+d-1과 y+d에 해당하는 점을 잇는 기울기, 우변은 x번 나무의 '덜 완성된' 도달비용 그래프에서 y-1과 y에 해당하는 점을 잇는 기울기처럼 보이게 된다. (기울기의 정의가 x축과 y축을 바꿔 그리는 바람에 (x증분)/(y증분)으로 바뀌어야 한다.)

이렇게 선분들로 쪼개서 보면 좋은 점이 하나 생긴다.
기울기가 바뀌는 점만 관리하고 있으면 된다는 것이다.
방금은 바로 아래 지점에서 올라오는 경우이기 때문에 1로 나누어줬지만 바로 아래가 아닌 이 나무(x번 나무)에서 계속 W[x]씩 들면서 한 칸씩 한 칸씩 올라왔던 거라고 생각해보면 정말 기울기로 판단해주는게 적합하다고 느껴질 것이다.

와우
다왔다 이제

이걸 그대로 구현한다면 N개의 나무마다 직선들을 관리해야 된다. 최적화를 잘해주면 통과할 것 같지만 더 쉬운 방법이 있다.
x-1번 나무에서 넘어올 때를 잘 살펴보면 저 수많은 직선들을 그냥 y축으로 -d만큼 평행이동시키는 거다.
그러고 평행이동된 그래프에 기울기가 W[x]인 직선 하나를 추가하기만 하면 x번 나무의 그래프가 완성된다!

그런데 직선들을 평행이동하는게 시간이 오래 걸린다. 문제없다. 어차피 상대적인 거니까 나무의 시작점과 끝점의 좌표를 y축으로 +d 해주면 같은 효과이다. 축을 평행이동시킨다고 봐도 된다.

축 바깥으로 나간 직선들은 고려 대상에서 제외해주고, 자투리 남는것들 잘 처리해서 구현하면 된다. 직선 관리는 CHT와 비슷하면서도 뭔가 좀 다르다. 그냥 컨셉만 CHT라고 생각하면 될 것 같다.

각 기둥마다 최대 직선 하나만을 추가하고, 각 직선은 한 번 들어왔다가 한 번 나가므로(CHT와 같은 논리) 시간복잡도는 O(N)이 된다.

부분점수 생각하면서 문제 읽어서 1~4번 문제 읽는 데 40분 정도 걸렸던 것 같고 그 이후로 4번 잡았는데 100점 떴을 때가 2시간 10분쯤 남았던 것 같다. 5시간인 선발고사의 반쯤을 이 문제에 꼴아박았기 때문에 좀 위험했었다고 생각한다. 실제로도 여기서 시간을 너무 많이 써서 1~3번을 다 못 긁고 끝났다. 버그를 내지 말았어야 했고, 생각도 좀 빨리 했어야 했다. 뇌절이 너무 심했다.

 

#include "squirrel.h"
#include <vector>
#define N 500005
using namespace std;

typedef long long ll;
struct st{
    ll a, b, st, ed;
} dq[N];

ll fr, bk;

ll fly(std::vector<int> D, std::vector<int> H, std::vector<int> W, int L, int R) {
    ll n = D.size();
    ll i;
    for (i = 0; i < n; i++) H[i] += D[i];
    dq[0] = {0, 0, 0, L};
    fr = 0; bk = 0;
    for (i = 0; i < n; i++) {
        while (fr <= bk && dq[fr].ed < D[i]) fr++;
        while (bk >= fr && dq[bk].st > H[i]) bk--;
        dq[bk].ed = min(dq[bk].ed, (ll)H[i]);
        if (fr > bk) return -1;
        bool v = 0;
        while (bk >= fr && dq[bk].a > W[i]) v = 1, bk--;
        if (v) {
            bk++;
            ll t = dq[bk].a * max((ll)D[i], dq[bk].st) + dq[bk].b;
            dq[bk] = {W[i], t - W[i] * max((ll)D[i], dq[bk].st), max((ll)D[i], dq[bk].st), H[i]};
        } else {
            ll t = dq[bk].a * dq[bk].ed + dq[bk].b;
            dq[bk + 1] = {W[i], t - W[i] * dq[bk].ed, dq[bk].ed, H[i]};
            bk++;
        }
    }
    R += D[n - 1];
    for (i = fr; i <= bk; i++) {
        if (dq[i].st <= R && R <= dq[i].ed) {
            return dq[i].a * R + dq[i].b;
        }
    }
    return -1;
}

풀이는 길지만 코드는 간단하다. (DP특)

 

 

+)

선발고사때 4번 생각하면서 썼던 건데 너무 난잡해서 앞에서 설명할 때는 그림을 새로 그렸지만 난 여기 그림들이 더 마음에 든다. 초록색 부분에서 가장 오른쪽 아래에 있는 그림이 최종 그림인데, 나는 저게 더 직관적으로 느껴지지만 다른 사람들에게 설명하기에는 너무 좋지 않은 그림이었다.
초록색 부분이 풀이 생각하는 과정, 파란색은 데이터 넣어서 검증한 과정이다. 검은색 x는 잘못되었거나 불필요한 계산이다.
위에 3번도 살짝 보인다.

---

4번을 맞고 기분좋게 4번 다음으로 친숙했던 3번을 고민하기 시작했다.
히스토그램 문제였는데, 적당히 DP랑 분할정복으로 접근하면 되겠지 싶었다.
근데 좀만 생각해보니

이런건 죽어도 못하겠는 거다.
그래서 시간 남으면 섭태 긁자고 생각하고 넘겼다.
섭태 1은 대충 견적 내놓았었고, k=1인 1점짜리 섭태의 섭태는 그냥 이 문제라서 할 수 있겠다고만 생각해뒀다.
결국 시간 없어서 1점도 못 긁었다.

---

이 다음로는 2번을 생각했다.
약간 문제가 생기면 적당히 빠른 해결방법을 생각해내는 방식으로 땜질하듯이 처리하고..이걸 계속 반복하다보니 시간 안에 돌아갈 것 같은 풀이가 나와서 구현을 시작하려고 했다.
그레이더 다운받고 코드를 짜기 전에 내가 뭘 어떻게 짜야될지 정리해보았다. (난 항상 코드를 짤 때 전체적인 흐름 구상을 마치고 짜기 시작한다. 이게 당연한 줄 알았는데 그냥 의식의 흐름대로 막 짜도 잘 굴러가는 사람도 있더라. 그는 구현의 신이야!)
와 근데 구현이 미쳤다. 그냥 해야될게 너무 많다. 와..
게다가 레이지 써야되는데 레이지 짜본지도 좀 돼서 구현을 막 물 흐르는 듯이 할 자신도 없었다.
짠다해도 300줄은 그냥 넘어갈 것 같아서 때려쳤다.

부분점수는 꽤 쏠쏠하게 긁었을 것 같은데 살짝 더이상 이 문제는 생각하기도 싫어서 1번으로 넘어갔다.

나중에 풀이 들으면서 안 건데 여집합을 이용하면 훨씬 쉬워지긴 하지만....여전히 너무 할 게 많아보인다.
아마 다들 구현때문에 거른 것 같다.

---

1번 생각하기 시작한게 한 1시간 40분쯤 남았을 때였다.
개인적으로 문제 스토리가 뭔가 레드 블랙 트리같은 느낌이었다. 특정 간선만 더해서 전체의 최대를 최소로 한다는 점이 그냥 그렇게 느껴졌다. 실제로는 많이 다르다. 사실 RBT에서 어려운건 로테이션이지 않나...이 문제에는 그런거 전혀 없다.

거의 직관적으로 그리디하게? 답을 구하는 방법은 찾을 수 있었다.
여기에 세그트리에서 업데이트 할 때처럼 노드가 새로 추가될 때, 그 노드의 조상만 다시 계산해주면 되겠다고 생각했고, 그러면 N, Q 범위 작은거(총 33점)랑 높이가 대충 lg n인 이진트리인거(5점) 한 번에 처리돼서 38점을 받을 수 있을 것 같았다.
근데 구현이 꼬여서 왠진 몰라도 제출했는데 계속 0점이 나왔다.
시간이 부족했기 때문에 33점만 긁는 단순한 코드를 짜서 제출했다. 근데 또 0점이다.
시간이 30분도 안 남았었기 때문에 막 이것저것 손대서 제출을 계속 했지만 결과는 같았다.
약간 포기하는 심정으로 코드를 다시 봤는데 인덱스 하나 착각한게 눈에 들어와서 고치고 실행 되는거만 확인하고 제출했다. 1분 20초? 남았었다.
채점되는 동안 데이터 이것저것 돌려보면서 맞는거 확인하고 이것도 0점이면 관두자고 생각했다.
다행히 33점이 나왔고, 그 상태 그대로 카운트다운 구경하다 끝냈다.

풀이를 들어보니 HLD 느낌으로 만점에 접근하는 것 같던데 잘 모르겠다. 결론만 놓고 보면 내가 38점 풀이가 맞으면 시도하려던 풀이랑 같은 것 같다..? 모르겠다.

---

선발고사 끝나자마자는 되게 기분이 좋았다. 실실 웃고있었을지도 모르겠다. 첫 제출에 뜬 4번의 영롱한 초록색과 끝나기 직전에 빨간색에서 바뀐 노란색이 너무 행복했다. 근데 밥을 먹으며 생각해보니 오늘 문제가 좀 쉬운 편이었고, 다른 사람들은 나보다 더 잘봤을 것 같아서 살짝 걱정이 되기 시작했다. 풀이 직전에 생각해보니 4번 100점이 막 20명쯤 나왔을지도 모르겠다는 생각도 들었다. 결과를 보니 그렇게까지 많지는 않았지만, 1번과 4번으로 분산되어서 그랬지 1번이 더 어렵게 나왔으면 진짜 15명정도는 나왔을 것 같다. 1번과 4번 100점이 둘다 꽤 많았는데, 두 문제 모두를 100점받은 사람은 한명뿐이어서 신기했다. 다들 시간이 부족했나보다.
나는 13등이었는데, 1, 2, 3번에서 못 긁은 부분점수를 착실하게 긁었다면 한 자리수 안에도 들 수 있었지 않았을까 싶어 좀 아쉽긴 하다. 근데 어차피 구현이 잘 풀렸어도 시간 부족해서 별로 못 긁었을 것 같긴 하다. 쨌든 만족스럽다.

풀이를 들으면서 4번은 좀 더 쉽게 만점으로 도달할 관찰들이 있었음을 알게 되었다.
그리고 이 글을 통해 다시 내 풀이를 되돌아보면서 내가 생각한 풀이지만 설명하기는 어렵다는 점에서 이해가 충분하지 않았다고도 생각하게 되었다. 푼 문제라도 다른 사람에게 설명해야겠다고 생각하며 다시 풀어보면 공부되는게 많을 것 같다. 근데 솔직히 나한테 저 위의 긴 풀이를 읽으라 해도 안 읽을것 같다...