JJaewon의 PS하는 블로그

제11회 한양대학교 프로그래밍 경시대회(HCPC) Advanced Division에 '신_섭이HCPC를정상화하네' 팀으로 참여했습니다. (jjaewon9, andrewmjk1, firstin0907) 보통 HCPC는 ICPC 팀원끼리 나가는 경우가 많은데, 저는 현재 휴학 상태라 HCPC를 같이 나갈 사람이 없었습니다. 그냥 아무나 데려가서 원맨팀이라도 해야하나 고민하던 찰나, 올해 ICPC에서 교내 1등을 한 BetterthanO1 (ingyu1009, andrewmjk1, firstin0907) 에서 ingyu1009이 검수로 런을 쳤다는 소식을 듣고 재빠르게 합류했습니다. 팀명은 팀원 세명 중 한명의 이름이 '신_섭'이라 그렇습니다 ㅋㅋ 팀연습같은건 안했고, 심지어 firstin0907님과는 대회 ..

Class 8을 달았다.Class 8에 처음? 등장하는 FFT / 플로우 / DnC opt 등을 공부하긴 귀찮고 그렇다고 국메기같은 굉장한 문제를 짜긴 싫어서, 최대한 구현이 편해보이고 이미 알고 있는 지식으로 풀 수 있는 문제들을 열심히 찾아서 풀었더니 딱 20문제가 됐다.  풀면서 재미 또는 감동이 있었던 문제에 대해 간략하게 사고과정과 풀이를 작성한다. 레드 블루 스패닝 트리 #4792더보기파란색 간선을 최소로 써서 MST를 만들어 그때 파란색 간선이 몇개인지 세고,파란색 간선을 최대로 써서 MST를 만들어 그때 파란색 간선이 몇개인지 세면,그 사이에 개수가 답이 될 수 있다. 풀이 자체는 n년 전부터 알고 있었는데, 이왕 푸는거 증명까지 해보기로 했다.현재 MST에 파란색 간선이 x개 있을 때, ..

대회 중뇌절했다. 대회 후인터넷 친구들과 링고에 다녀왔다.

UCPC 2022에 sean9892, pentagon03 와 함께 참여했다. 3명 모두 공대 새내기라, 새내기들을 괴롭히는 과목들인 일물실, 일화실, 캘큘을 닉네임으로 하고 팀명을 '새내기 개노답 삼형제' 로 지었다. 대회 전팀 연습은 3번정도(나는 한번 빠졌다) 설렁설렁 했고, 팀연습과 이번 예선 모두 디스코드를 이용해 각자 치뤘다. 전날 했던 SUAPC 2021 Winter 팀연습에서 나름 좋은 폼을 보여줬기 때문에, 괜찮은 결과를 기대하며 예선에 임했다. 대회 초반ABCD(sean9892) / EFG(jjaewon9) / HIJ(pentagon03) 으로 분할해 문제를 먼저 읽었다.역시나 A가 가장 쉬운 문제였고, sean9892가 의문의 RTE를 한번 받은 후 AC를 띄웠다.04:19 A RTE ..

Link https://www.acmicpc.net/problem/17635 APIO 2019 2번 Tag Union-find 오프라인 쿼리 평방 분할 Time Complexity $O(Q \times (\frac {M}{B} lgM + B^2lgB))$ $(B=BucketSize)$ 정점 $N(\leq 50,000)$개, 간선 $M(\leq 100,000)$개인 그래프가 주어진다. 1. $i$번 간선의 가중치를 $w$로 변경 2. 정점 $v$에서 가중치가 $w$ 이하인 간선들만 거쳐서 도달할 수 있는 정점의 개수를 출력 두가지 쿼리가 $Q(\leq 100,000)$개 주어진다. 오프라인으로 처리해도 된다. 1번 쿼리가 없을 때는, 간선들을 가중치의 내림차순으로 보면서 컴포넌트의 크기를 세주기만 하면 된..

2022 숭고한 연합 알고리즘 콘테스트에 Division 2로 참가해 2등을 수상했다. (빨갛게 빛나는 10틀) 아쉽긴 하지만, 대학 진학 후 첫 공식? 대회에 나름 좋은 성적을 거둬 기쁘기도 하다. 대회 전 Division 2의 참가조건은 숭실대 SCCC / 고려대 Alps / 고려대 Alkor / 한양대 Aloha 의 부원이면서 ICPC, SCPC, UCPC, KOI 등 수상 X / solved.ac D3 미만 / Codeforces max rating 1900 미만 이며, 난 한양대 Aloha의 부원이고, 대회 수상이 없고, solved.ac P1, 코포 맥레가 1900이 조금 안돼서 Division 2에 참가했다. 대회 신청 후 공지를 읽어보는데 처음에는 zoom을 이용해 참가자 캠과 화면 녹화를..

Link https://www.acmicpc.net/problem/21607 2021 SciCom Qualification Test 2E번 Tag Segment Tree Spare Table Time Complexity $O(Q(lgN+lgQ)+XlgX)$ $(X=100003)$ $f(x)=2x^2-1, g(x)=4x^3-3x$이고, 길이 N의 수열 $A$가 주어진다. $f,g$를 구간에 적용하는 쿼리와 $A_i$를 $100003$으로 나눈 나머지를 구하는 쿼리가 주어진다. 이러한 쿼리를 $Q$개 처리해야 한다. 일단 $f,g$가 곱셈으로만 이루어져 있으니 나머지를 구하는건 그냥 해주면 될거 같고, $f,g$를 어떻게 하느냐가 문제다. 근데 왜 하필 $f,g$를 저렇게 줬을까? 뭔가 특별한 성질이 있나?..

제 6회 국민대 알고리즘 대회에 참가했다...! 작년에 본선에서 화장실 이슈(?) 로 아쉽게 장려상을 받아서 이번에는 정말 열심히 준비한..... 건 아니고 그냥 무지성으로 신청했다. 문제를 공개하면 안되나? 그래서 풀이는 대충 쓰도록 하겠다. 예선 올해도 온라인으로 1시간동안 진행됐다. 원래 12시 반 ~ 1시 입실에 2시 시작인데, 뭔가 문제가 있었는지 1시 이후에야 입실이 가능했다. 뭐 2시 시작이라 진행에 차질이 생기지는 않았다. 1번은 2차원 부분합을 구하는 문제였는데, 문제 지문에 대놓고 'prefix sum을 써라'고 적혀있었다. 뭘까.... 2번은 대충 pq에 pair박으면 된다. 200점 15분컷내고 본선에 진출했다. 본선 본선은 국민대학교 미래관에서 2시~4시에 오프라인으로 진행되었다...

Link https://www.acmicpc.net/problem/16909 Tag 스택 Time Complexity $O(N)$ 수열 $A$가 주어지고, $A$의 모든 구간 $[s,e]$의 최댓값-최솟값의 총 합을 구하는 문제다. 최댓값의 총 합과 최솟값의 총 합을 각각 구하자. 각각의 $A_i$에 대해 $A_i$보다 왼쪽에 있으면서 $A_i$보다 큰 수 중 가장 오른쪽에 있는 수의 인덱스를 $s_i$, $A_i$보다 오른쪽에 있으면서 $A_i$보다 큰 수 중 가장 왼쪽에 있는 수의 인덱스를 $e_i$이라 하자. 그러면 구간 $[a,b]$ $(s_i \le a \le i \le b \le e_i)$ 의 최댓값이 $A_i$가 된다. 그러한 구간의 개수는 $(i-s_i)(e_i-i)+e_i-s_i+1$이다..

국민대학교에서 알고리즘 대회가 있었다. 왠만하면 본선은 붙지 않을까 + 붙으면 서울 구경이나 해야지 하는 생각으로 예선을 신청했는데... 예선 예선은 온라인으로 한시간동안 진행했다. 캠 켜고 핸드폰 켜고 귀찮았다. 1번은 어디서 많이 본 문제였다. https://codeup.kr/problem.php?id=3095 걍 뚝딱 풀었다. 4분? 2번은 사다리타기를 시뮬레이션 하는 문제였다. 간선이 10만개였나? 간선을 단방향으로 분리해서 생각해보면 어차피 한번씩밖에 안지나간다. 그래서 대충 lower_bound 같은거 때려가면서 $O(lgN)$에 간선 따라가는 풀이를 구상했다. 어... 근데 구현이 어렵더라. 한시간 내내 디버깅하다 결국 제출 한번 못해보고 시간이 끝났다. 문제는 둘 다 쉬웠다. 근데 내가 개..