오늘은 태훈이가 앞쪽, 내가 중간, 남일이가 뒤쪽 문제를 봤다. 내가 3시간도 자지 못해서 컨디션이 많이 안 좋았었다... 대회날에는 컨디션 관리를 잘 해야할 듯 나는 E,F,G,H를 모두 읽었는데 풀 수 있는 문제가 하나도 없어서 당황했다... 그 사이 태훈이가 문제를 하나씩 풀기 시작했다. 00:07 태훈이가 A를 풀었다. 00:23 태훈이가 B를 풀었다 00:37 태훈이가 C를 풀었다. 태훈이가 엄청난 퍼포먼스로 골드급 문제를 빨리 밀어줘서 내가 상대적으로 어려운 문제들을 오래 고민할 수 있었다. 나는 K를 BCC로 풀 수 있겠다고 생각하고 풀이를 정리하고 있었다. 01:08 그 사이 태훈이가 I를 풀어냈다. 대단... 나는 K의 풀이를 코딩하고 나서 시간복잡도가 예상보다 제곱배로 크다는 걸 깨닫고..
00:13 오늘도 내가 앞부분 문제를 읽었다. A랑 B가 뭔가 할만해 보이게 생겼었는데 스코어보드에 C솔브가 올라와서 내가 C를 읽고 풀었다. 급한 마음에 타이핑을 실수해서 한 번 틀렸다... 00:44 그 다음으로 K가 많이 풀리길래 내가 K를 읽고 풀었다. 이 문제는 코딩을 좀 더 빠르게 했었어야 할 것 같다. 01:16 태훈이가 펜윅을 짜고 F를 풀었다. 실수로 한 번 틀린 것 같다. 01:42 내가 E를 읽고 아호코라식+dp 풀이를 만들었는데 구현하기가 막막했다... 일단 팀노트에 있는 아호코라식 코드를 옮기고 열심히 코딩을 했는데 예제가 안 나왔다. 키보드를 넘겨주고 문제를 다시 읽어보니 빼먹은 조건이 있어서 다시 키보드를 뺏고 고쳐서 맞았다. 02:21 남일이가 H에서 고전하길래 내가 문제 설..
약간 아쉬운 성적인 20등으로 마무리했다. 팀연습 때처럼 로봇융합관에 모여서 했는데 도중에 에어컨이 꺼지는 이슈가 있었다. 그것때문에 제 퍼포먼스를 발휘하지 못한 거라고 정신승리를 하기도 했다. 00:01 구현이 빠른 태훈이가 A를 읽기로 했고 퍼솔을 먹었다. 00:17 문제들을 쭉 한 번 훑어보고 내가 가장 쉬워보이는 B를 풀었다. 00:20 태훈이가 아마도 구현문제였던 E를 풀었다. 그 뒤로 약간 정체가 있었는데 나는 D에서 '분수 이분탐색? 설바 stern-brocot 트리인가?' 하며 뇌절을 했다. 실제로 전명우 선배님 블로그를 보며 stern-brocot 트리를 공부하려고 시도했었다. 00:42 남일이가 J의 풀이를 알아내고 맞았다. 01:01 태훈이가 F를 밀어줬다. 01:08 D가 생각보다 ..
00:13 내가 앞부분 문제를 읽고 B를 풀었다. 실수해서 한 번 틀린 건 그럴만 한데 스코어보드를 잘못봐서 B를 늦게 읽은 건 반성해야겠다. 00:21 내가 A를 제출했지만 틀렸다. 다시 생각해보니 풀이에 반례가 존재했다. 00:34 태훈이와 남일이가 상의를 하고 H를 풀었다. 00:55 내가 A에 꽂혀있는 사이 태훈이가 D를 읽고 풀었다. 내가 조금 더 일찍 읽었어야 했던 거 같다. 01:26 G는 실수+기하라 풀기 싫었지만 그다지 어렵진 않은 것 같아서 내가 풀었다. 이분탐색 구현을 실수해서 한 번 틀렸다. 01:41 남일이가 I를 짜고 제출했지만 틀렸다. 풀이는 들어봤는데 맞는 것 같았다. 01:50 태훈이가 K를 풀었다. 02:07 남일이가 I의 틀린 부분을 알아내고 맞았다. I의 아이디어는 나..
만약 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$에 대해 아래로 볼록한 형태를 띈다. 따라서 실수라는 점이 다소 불편하지만 이분탐색으로 최소값을 구할 수 있다. 따라서 수열을 고정시키는 방향으로 ..