만약 Alien Trick에 대해 이미 알고 있다면 절취선 아래의 내용만 읽어도 도움이 될 것입니다. Alien Trick이 알려지기 시작한 것은 IOI 2016 이후이며 아직까지도 많이 알려지지는 않은 알고리즘이다. 나 같은 경우 2019년에 Alien Trick을 공부하였는데 구현한 코드를 찾지 못하여 구현에 어려움을 겪었다. 이 글을 통해 더 많은 사람들이 Alien Trick에 대해 알았으면 좋겠다. koosaga 님의 글 과 imeimi 님의 글 을 먼저 읽고 오면 좋다. 내가 KCPC 2020에 출제한 문제를 바탕으로 설명을 하겠다. $Cost[i][j]$를 부분수열 $a[i...j]$에 존재하는 서로다른 수의 개수로 정의하자. $dp[i][j]$는 부분수열 $a[1...j]$를 $i$개로 쪼..
Intro ICPC 서울리저널에서 7등을해서 교내 1위, 대학순위 3위를 기록했다! 팀원은 cheetose,ryute,knon0501(나) 이다. 고대에서 잘하는 두 팀(Powered by zigui, 1WA=5 push up)이 모두 은퇴를 해서 교내 1위는 할 것 같았다. 연초에는 3오렌지 정도면 충분히 월파를 노릴만하다는 생각을 했으나 UCPC와 ICPC 예선을 말아먹으며 갈수록 자신감이 똑떨했다... 그래도 팀연습을 10번이나 했고 나는 2학기를 ICPC준비에 올인할 생각으로 17학점을 전부 꿀과목으로 채웠다. 팀연습을 많이 한 것이 패널티를 줄이는 데에 정말 많이 도움이 된 것 같다. 본선에서는 팀원 모두의 강점이 드러나서 좋은 결과를 얻었다. 월파를 갈 수 있을 진 모르겠는데 가면 좋겠다 ㅋㅋ..
www.acmicpc.net/problem/2431 삽질을 많이 해서(그럴만한 문제다) 4시간 정도 때려박아서 풀었다. 문제를 다시 써보면 다음과 같다. 수열 $x_1,x_2,...,x_n$ 이 주어졌을 때 이 중 몇 원소에 -1을 곱하고 오름차순으로 정렬하자. $y_i=k+(i-1)\cdot \frac{2m}{n}$로 정의할 때 적당한 $k$를 골라 $\left| x_1-y_1 \right| +\left| x_2-y_2\right| +...+\left| x_n - y_n\right|$ 을 최소화시켜라. 수열 $x_i$가 고정되었다면 구하고자 하는 값은 $k$에 대해 아래로 볼록한 형태를 띈다. 따라서 실수라는 점이 다소 불편하지만 이분탐색으로 최소값을 구할 수 있다. 따라서 수열을 고정시키는 방향으로 ..
2020 숭고한 연합 알고리즘 캠프 후기를 씁니다. Contest 와 Maraton을 분리해서 작성합니다. Maraton은 안 쓸수도.. ALPS에서 운영진을 맡고 있지만 숭고한은 참가자로 나갔습니다. 이유는 이미 출제진이 충분히 많았고 ALPS에서 문제제작 스터디를 진행하고 있었고 시험기간이 겹치는 상황이었고 등등 여러가지가 있습니다. 결과적으로 1등을 해서 40만원을 받게 됐습니다. 사실 저보다 잘하는 사람들이 꽤 많이 나와서 대상은 바라지도 않았고 최우수상이라도 받을 수 있을까 걱정했는데 결과가 좋아서 기뻤습니다. 문제는 Advanced(Div.1) 기준 A부터 I까지 9문제이고 저는 A,B,C,D,F,G를 해결했습니다. 작년 숭고한은 Educational하고 쉬운 문제들로 구성되었는데 이번에는 난..