돌이 코딩하는 방

이미 결말이 어느정도 알려진 스토리지만, 또 전지적 주인공 시점에서의 이야기는 또 다르니 한번 후기를 작성하려고 한다. 벌써 키보드를 두드리는 소리가 경쾌하다. 0. Prologue 다시 소개를 하자면 저희의 팀명은 DolAndDool 이며 팀원은 gs25, stonejjun03, yijw0930 이다. 우리팀의 포지션은 yijw가 자료구조와 역겨운 구현들을 맡고, 본인이 아이디어 및 관찰을 맡으며, gs25가 관찰, 수학 및 서포팅을 맡는다. 팀연습을 통해서 yijw-gs25 조합이 수학 문제 해결이나 gs가 툭 던져 yijw가 구현으로 마무리 하는 호흡을 보여주었으며, 특히 stonejjun-gs25 조합이 관찰을 엮거나 툭 발전시키기, 풀이의 큰 틀 잡는 감은 훌륭하지만 풀이의 완성도가 떨어지..

대회 준비 과정은 이 글 에서 볼 수 있습니다.0. Prologue다시 소개를 하자면 저희의 팀명은 DolAndDool 이며 팀원은 gs25, stonejjun03, yijw0930 입니다.팀의 큰 목표는 월드 파이널 진출이기 때문에 아시아 리저널 진출이 1차 목표이지만, 두 명 모두 서울 리저널 수상 경험이 없기 때문에 수상 또한 목표입니다.다만 포스텍,연세대,서강대,한양대 등의 늘있는 수상권 근처 wwe 뿐만 아니라 너무 많은 잘하는 서울대/카이스트 팀이 본선에 진출한 것이 큰 악재였습니다.예비 소집 날 갑자기 마라샹궈가 먹고 싶어졌으며, 매운 것과 ps 실력 어쩌고의 밈도 생각나서 마라샹궈 크게 한 대접을 저녁으로 먹었습니다. 좀 불안했지만 푹 자라, 마음을 비워라, 유튜브나 봐라라고 조언한 kar..

0. Prologue오랜만에 복귀하여 ICPC 2024를 위하여 적당히 달려왔습니다. 결론부터 말하자면 얼마 전 2024 ICPC seoul regional 수상으로 마무리하였고, 아마 1차 목표인 아시아 퍼시픽 리저널에 출전할 수 있을 것으로 보여집니다. 그 긴 여정과 마지막 대회까지의 긴 이야기를 적어보려고 합니다. 1. Coding Dol and Dool 작년에 모종의 이유로 예선에도 나갈 수 없었지만, 올해 yijw0930과 함께 팀을 하기로 말해 놓았습니다. 미리 말해놓지 않았으면 빼앗겼을, 고려대에서 굉장히 중요한 인물이었기 때문에 이는 최고의 선택이 되었습니다.   gs25는 2~3년 전쯤에 적당히 찍먹하고 접었습니다. 그러다가 작년 11월부터 다시 열심히 시작했습니다. 기본적으로 수학올림피..

따로 글을 쓰기에는 애매한 문제들이 있고, 그래도 풀이를 간단하게라도 정리하는 것이 필요해서, 다른 사람들의 방식을 빌려서 정리하려고 한다. 보통 플레 수준의 문제. 이번에는 8월 달에 문 문제도 일부 포함되어 있다. BOJ 7036 Grazing on the Run 풀이 더보기 DP 향이 강하게 난다. 특히 파일 합치기 느낌으로 dp[i][j] = i~j 의 구간관리. 일단 첫번째로 구간 i~j 의 모든 건초를 먹었으면 위치 i또는 j에 있을 것이다. 따라서 [i][j][k] 에서 k로 최종적으로 i에 있는지 j에 있는지를 확인하자. dp[i][j][k]에 어떻게 값을 저장할 지가 핵심이다. 구간을 다 먹었을 때 최소치만을 고려하면, 지금까지 걸린 시간에 따라서 앞으로 먹을 건초가 달라지기 때문에 최소..

Chap 0. Prologue 2차 예선에서 탈락의 고배를 마신 작년과 달리 올해는 본선에 진출할 수 있었다. 그렇기 때문에 더욱더 상이 간절해졌다. 5등상이기만 해도 부수적으로 얻을 수 있는 것들이 많았기 때문에 SCPC 수상이 정말 간절했다. 올해의 CP 3대 목표는 scpc 수상, icpc 월파 진출, 코포 레드 달성이다. 예선은 굉장히 나답게 통과했다. 4번은 힘을 들이지 않고 풀이가 생각났는데 3번은 죽어도 풀이가 안떠올랐다... 불안해서 열심히 긁었고, 안정적으로 본선에 진출할 수 있었다. Chap 1. 본선 준비 icpc ucpc와 scpc의 차이는 무엇일까. 첫째로 개인대회라는 것이고 둘째로 팀 노트가 없다는 것이다. 그렇다면 코포와 scpc의 차이는? 검색이 안된다는 것이다. 그렇다. 모..

문제 링크 : https://www.acmicpc.net/problem/8189 문제 풀이 일단 문제를 보면 몇 가지 사실들을 알 수 있다. 첫 번째로 답이 가능한 길이는 짝수이다. 좀 더 생각해보면 답이 가능할 조건을 다른 방법으로도 판단할 수 있다고 생각할 수 있다. 예를 들면 반으로 접었을 때 만나는 두 원소의 합이 모두 1일 때 Antisymmetry이다. 중요한 것은 1010101010... 과 같은 경우에 답의 스케일이 $O(N^2)$이기 때문에, 답의 개수를 하나하나 구하는 것은 불가능하다고 판단할 수 있으며, 따라서 (어떠한 조건의 ) 문제에서 구하고자 하는 구간의 개수를 한번에 구함으로서 문제를 해결하는 쪽으로 방향을 잡을 수 있다. 보통 구간과 같은 경우에는 동일한 시작점 혹은 끝점으로..

문제 링크 : https://www.acmicpc.net/problem/19265 문제 풀이 이 문제는 배열 p에 존재한 모든 $p_i$에 대해서 $T_i = Tp_i $ 인지를 S의 모든 구간에 T에 대해서 확인하는 문제이다. 여기서 어떤 형태를 비교하는 거니까 문자열 매칭과 비슷한 느낌을 받을 수 있다. 먼저 생각난 것은 KMP 였지만 KMP로는 풀 수 없는 형태였다. 실패함수가 좋은 형태로 나타나지 않기 때문에 KMP는 포기할 수 밖에 없었다. 이 상태에서 문제를 푸는 사고의 흐름이었다면 라빈-카프 해싱을 생각을 했어야 했다. $T_i = Tp_i $ 라는 것은 i 기반 해싱값과 pi 기반 해싱값이 같다는 거고, 좀 만 더 생각하고 식을 변형 시켜 보면 $\sum_{i}^{} i\times T_i ..

문제 링크 : https://www.acmicpc.net/problem/8103 문제 풀이 가능한 위치가 직사각형으로 주어진다. 직사각형이기 때문에 y 좌표가 가능한 범위는 x 좌표에 영향을 받지 않는다. 따라서 x와 y를 따로 놓고 생각해서 구할 수 있다. 주어진 문제를 축 별로 쪼개서 본다고 하면, 구간이 n개 주어지고 n개의 구간에서 각각 수를 하나 씩 뽑아야 하는데 이 수가 1~n까지 서로 다른 수여야 한다. 위의 문제를 어떻게 풀 수 있을까? 이미 1~i-1 까지 배정을 했다고 하자. 이제 i를 어떤 구간에다가 배정해야 할 지 골라야 한다. 가능한 구간은 s~e에서 s가 i보다 작으며, e가 i보다 큰 구간들이다. 이러한 구간들에서 e가 가장 작은 구간을 뽑는 것이 이득이다. 앞으로 가능한 구간..

문제 링크 : https://www.acmicpc.net/problem/10169 문제 풀이 부분 부분 알고 있었던 내용이었다. 간선이 하나씩 없어지는데 각각의 경우에 MST 길이 합을 구하는 문제이다. 가장 먼저 생각할 수 있는 부분은 맨 처음에 전체 그래프에서 MST를 구해서 MST에 쓰이는 간선과 쓰이지 않는 간선을 나눌 수 있다는 것이다. 또한 거기에 더해서 첫 MST 에 쓰이지 않는 간선들은 제외를 해도 길이 합이 변하지 않는 다는 것 까지 알 수 있다. 그렇다면 첫 MST에 쓰인 간선이 지워졌을 때 대체하는 최소 비용의 간선을 모든 간선에 대해서 다 구해야 한다. 그 이후로는 이 문제의 경험이 굉장히 도움이 되었다. MST에 속하지 않은 간선 들은 cross edge 또는 back edge가 ..

문제 링크 : https://www.acmicpc.net/problem/3682 문제 풀이 최소 간선을 추가해서 전체를 하나의 SCC로 만드는 문제이다. 먼저 주어진 그래프를 생각해보자. 애초에 문제에서 하나의 SCC 로 만드는 것이 목표이기 때문에 그래프를 SCC 간의 위상정렬로 놓고 생각하지 않을 이유가 없다. 따라서 그래프에서 먼저 SCC를 구하자. SCC 내에서는 서로 동치이기 때문에 추가적인 간선을 이을 필요가 없다. 따라서 처음에 구한 하나의 SCC 는 하나의 정점으로 대체하여 생각할 수 있다. 그렇게 변형된 그래프를 생각해보자. 그래프에는 사이클이 존재하지 않는다. 여기서 모든 정점을 묶어서 SCC로 만들어 주어야 한다. 이를 위해서는 모든 정점의 outdegree와 indegree가 1 이..