2019 숭고한 세미나

2019 숭고한 세미나

올해 8월 초에 열린 숭고한 연합 세미나에 참가했다. 복귀 이후 UCPC 예선을 말아먹은 것을 제외하면 처음으로 관련 행사에 참가하는 것이다. 각 실력에 맞게 초급/중급/고급반에 신청해 각 수업을 듣는데, 같은 시간대의 다른 division의 수업 또한 들을 수 있다. 다만 마지막 날 있는 대회의 양민학살을 막기 위해 다른 반의 수업을 두번 이상 듣게 되면 들었던 division의 가장 높은 division으로 참가해야한다.
오랜만에 사람들을 만난다는 설렘 반 두려움 반으로 상경해서 학교에 갔는데, 익숙하면서도 조금씩 바뀐 풍경과 알지 못하는 사람들이 그득해서 어색하게 자리에 앉아 홀로 강의를 들었다. 일정이 오후 1시부터 9시까지 상당히 늦게까지 진행됐지만 개념의 설명과 그 적용을 하는데엔 그 시간도 부족한 적이 있어, 일정이 끝나더라도 귀가 후 못 다 푼 문제를 풀고 새벽에 잔 적도 꽤 있다. BOJ에서 그룹 연습으로 진행했는데, 스코어보드 위에 올라가겠다는 욕심이 있는지 재제출하는 빈도가 꽤 높았다.
그래서 항상 스코어보드에서는 중간정도만 갔었는데, 마지막 대회에선 어째서인지 중급 divison 대회에서 1등해버렸다?? 중급은 다 푼 사람도 없이 혼자 다섯문제로 1등을 먹었지만, 고급 division은 고인물들의 파티였다. 올솔브가 난무하는 가운데 패널티와 점수차이로 수상권이 갈렸다. 부상으로 받은 기계식 키보드는 부모님 컴퓨터에 놔드렸다. 텐키리스라서 집으로 돌아가기 전에 용산에 들려 텐키패드와 USB연장선을 사 같이 달아드렸다. 거의 20년정도 쓴 삼성제 DT-35는 이제 안녕!

대회문제 복기

1. 이건 꼭 풀어야 해!
   간단한 0제출 방지용 문제였다. 물론 naive하게 합을 구하면 TLE가 뜨고, 누적합 배열을 써서 B-A의 값을 출력하면 됐다.
2. 무한 부스터
   사실 문제 처음부분만 읽고 복잡할 것 같아서 다른 문제를 먼저 잡았다. 하지만 거의 난이도 순 배열이였고, 쉬웠다. 간단히 테이블을 MAX값으로 채우고, 각 map에 있는 부스터 범위 수 만큼 누적 부스터 수를 min값으로 갱신하고 n,m위치의 값을 출력하면 됀다.

3. 이진수 변환
   문제는 난해했지만, 솔루션은 간단했다. 다만 명제를 세우고 그게 반례가 없다는 것을 믿고(또는 증명하고) 비트연산을 할 수 있어야 풀 수 있는 문제였다. 일단 주어진 수 k가 2진수 비트로 표현 했을 때 n보다 작다면 n번 변환을 할 수 없으므로 -1을 출력하고 끝낸다. 그 외에는 가장 앞에 있는 비트를 하나씩만 변환해 가다가 n번째 변환에서는 0으로 만들면 됀다.

   for (int i = 1; i < n; i++)
   {
        while (!(k & (1LL << bc))) bc--;    //bc: 가장 앞 비트의 위치
        k &= (1LL << bc) - 1;       //가장 앞의 비트를 0으로 변환
        printf("%lld ",k);
   }
   

   비트수를 세고 가장 처음 비트를 찾는 전처리를 제외하면 전체 솔루션은 이게 끝이다!

4. 백도어
   전형적인 다익스트라 문제다. C번 이진수 변환의 증명이 조금 확실하지 않아 머리를 비우고 풀 수 있는 이 문제 먼저 잡았다. 와드가 깔린 정점은 간선을 넣지 않고 다익스트라를 돌리면 됐다. 간단한 솔루션이어서 대회 처음부터 제출이 됐지만 계속 WA가 뜨고 첫솔브가 대회 후반부에 나왔다. 그 이유는 최단경로의 길이가 int범위를 넘어서 long long을 써야 했지만 아무도 그 체크를 안하고 문제가 잘못된거 아닌가 하고 놓고 있다가 후반에 누군가가 풀고 나서야 무수한 솔브가 생겼다(…)
5. FLEX
   3차원 DP문제다. DP라는 것은 빨리 알아챘지만 점화식은 문제를 종이에 끄적여가면서 생각의 흐름을 전부 써내려가다가 만들었다. (두 장정도를 끄적였다) 그래서 아직도 이 점화식이 직관적으로 이해가지 않는다. 그래도 돌아가니 메데타시 메데타시…?
   만든 점화식은 ans[d][mm][k] = min(ans[d][mm][k], ans[d-1][mm-k][l] + cost(arr[d - 1]+l, arr[d]+k )); 로, 각각 날짜, 지금까지 쓴 여윳돈, 오늘 쓸 돈이다. DP의 냄새를 강하게 풍기고, 그렇게 변태적인 테크닉은 없어서 많이 풀 수 있을거라 생각했는데 의외로 나를 포함해 두 명밖에 풀지 못했다. 다들 다익스트라의 long long에서 멘탈이 나갔을 것이라 생각한다. 아니면 이걸 이렇게 못 풀리가 없어…
6. 통신망 분할
   disjoint-set을 이용한 문제라고 적어두고 더 이상 보진 않았다. disjoint-set은 개념은 쉽지만 응용이 너무 어렵다…
7. 트리의 외심
   LCA문제라고 생각은 했는데, LCA를 세 정점에 대해 돌리는 것이 이상적인 솔루션이지만, 불가능한 경우를 체크하는 것이 필요하다. 그 과정에는 역시 disjoint-set이 들어간다. 두 정점의 공통 조상중에 또 다른 정점이 들어가있다면 불가능하다고 메모해뒀다. 그리고 그 외에도 다른 불가능한 경우가 있을 것 같은데 찾지 못했었다. 공식 풀이와 출제자의 블로그에 정해가 올라와 있는데, 보다 보면 대회때 저런 증명을 하지 못하면 직관적으로 캐치해내는 센스가 필요하다는 걸 느낀다. 그게 실력이겠지.

• 공식 editorial이 있다.

총평

좋은 수업과 대회, 그리고 스폰서가 합쳐져 재밌는 세미나였다! 오랜만에 만난 선배와 동기들도 있었고(후배는 아무도 몰랐다 ㅠㅠ), 당보충을 할 수 있게 초콜릿같은 간식이 있는 것이 9시까지 이어지는 강행군을 버틸 수 있게 했다. 다만 너무 오랫동안 있는 것이 부담됐는지 저녁먹고 탈주하는 인원이 많았다. 그리고 첫날 수업을 중급반이 아닌 고급반에서 세그먼트 트리를 들을 걸 하고 후회했다. 다익스트라와 플로이드는 많이 했지만, 이번에 다시 공부한다는 마음가짐으로 들었지만 역시 세그먼트를 들었어야 했다.