79brue의 PS 블로그

최근 몇 달 동안 SciOI 2023 준비 외에는 PS를 거의 안 했는데, 방학을 맞은 김에 재활용으로 문제 몇 개를 풀어보기로 했다. 랜덤 플래티넘 디펜스를 했다. (곧 SciOI 2023 후기가 올라갈 수도 있을 것 같다.) BOJ 4284. A Walk Through the Forest 간단한 다익스트라 + DP 문제다. 집에서부터 시작해서 다익스트라를 돌리고, 집에서 거리가 멀어지는 순으로 정점들을 정렬한 뒤 가능한 가짓수를 DP로 계산하면 된다. 시간 복잡도는 $\mathcal{O}(N+M \log M)$이다. BOJ 29769. 음악회 평균의 최댓값은 수열의 최댓값이다. 즉 수열에서 최댓값이 가장 많이 연속한 구간 중 가장 긴 것 중 가장 왼쪽에 있는 구간을 찾으면 된다. 수열 A 이외에 수열..

역사적인 solved.ac 아레나 첫 대회에서 모든 문제를 풀어 4등을 했다. 한동안 OI style의 문제들만 풀다 ICPC style의 문제들을 접하니 조금 난감했는데, 다행히도 운이 좋아 좋은 성적을 받았다. 대회가 성공적으로 마무리된 점은 한국 PS계에 상당히 고무적일 것으로 보인다. 아레나 시스템에 대한 다양한 생각을 해봤는데, 이런 이야기들은 후기 끝에 짧게 써 보겠다. A. 양말 짝 맞추기 (0:00:31) 다섯 개의 수 중 한 번 등장하는 수를 찾는 문제이다. 다양한 풀이 방법이 있지만, 다섯 개의 수를 XOR하는 것이 가장 코딩하기 빠르다. 더보기 #include using namespace std; typedef long long ll; int a, b, c, d, e; int main..

https://www.acmicpc.net/problem/17697 17697번: Railway TripJOI Railways is a company operating one railway. In the railway of JOI Railways, there are N stations on a straight line numbered from 1 to N. For each i (1 ≤ i ≤ N − 1), the station i and the station i + 1 are connected by a railway track. JOI Railwwww.acmicpc.net$N$개의 역이 일렬로 있으며, $i$번 역의 등급은 $A_i$이다. 모든 $A_i$에 대해 $1 \le A_i \le K$가 성립한다..

아실 분들은 알고 계셨겠지만, 그동안 SoundCloud 계정을 운영하고 있었습니다. 지금까지 틈틈이 작곡해온 곡들 중 일부를 업로드해 놓았으니 많이 들어주시면 감사하겠습니다. https://soundcloud.com/chzsa6zxf2km 79brue Listen to 79brue | SoundCloud is an audio platform that lets you listen to what you love and share the sounds you create. soundcloud.com

역시 지난번의 굿바이 한별 팀으로 참가해 종합 9등을 했다. 나는 정말 최악의 대회를 치른 것 같다는 느낌이었다. 다른 팀원들이 그나마 많이 풀어 줘서 이 정도라도 올라온 것 같았다. CD. Colored-Dealt (0:13:25) 나는 처음에 AB, CD, EF, GH, IJ를 맡기로 했는데, 일단 CD를 읽자마자 쉽다는 확신이 들어서 바로 잡았다. 우선 전부 다 빨간색으로 배정하고, 왼쪽부터 한 개씩 푸른 색으로 바꿔나가는 식으로 최대 가중치 구간을 한 칸씩 이동시킬 수 있다. 이때 인접한 두 쿼리의 차이를 이용해 $N-1$개의 꽃 색을 알 수 있고, 마지막의 경우 첫 번재 쿼리 결과를 이용해 알아낼 수 있다. #include #include "colored_dealt.h" #include usin..

곧 있을 2023 함수컵을 대비해 2019 함수컵을 풀어 보았다. 굿바이 한별(79brue, flappybird, lisifu) 팀 연습 세션으로 5시간 동안 돌아 1068/1200점, 대회 중 2등의 성적을 기록했다. 나는 저 중 1-1, 1-2, 1-3, 2-1, 4-1을 맡았다. 1-x 문제들은 매우 쉬운 문제들이었기 때문에 사실상 2-1 푼 게 유일한 기여라고 할 수 있겠다. 4-1도 원래 무조건 풀었어야 했을 문제인데, 못 푼 게 아쉽다. 나머지 문제들 중에서는 어려운 게 많았는데 팀원들이 대부분 너무 잘 풀어줘서 고마웠다. A. HicCup (0:13)$X$에 대한 이분 탐색을 한다. 간단한 스택 문제이다. 스택을 통해 현재 상태를 오토마타 느낌으로 저장한다. 현재 상태는 H, HC, HC!!..

싱가포르 NOI 2022를 돌아 364/500점을 받았다. [BOJ 27288] A. Voting Cities (0:13) 바로 몇 주 전에 동아리에서 랜덤 플래 풀기를 하다가 본 문제라서 바로 풀었다. 기본적인 아이디어는 $K$개의 정점을 시작점으로 두고 한번에 다익스트라를 하면 되는데, 다익스트라에 상태 $d$를 추가적으로 저장한다. $d$는 사용한 쿠폰 목록이다. 아직 쿠폰 가격은 모르므로 쿠폰 가격은 쿼리를 처리할 때 더하도록 하자. 이후 쿼리가 들어올 때는 $32$가지 $d$를 고르는 경우 중 가장 싼 것을 고르면 된다. #include using namespace std; typedef long long ll; struct dat{ int x, d; ll y; dat(){} dat(int x,..

COI 2022 (크로아티아) 를 돌아 네 문제 중 세 문제를 풀어 334점을 받았다. 400점을 받아야 했을 셋인 것 같은데 아쉽다. [BOJ 25447] D. Vingete (00:18) 화성 지도 세그를 알면 매우 쉽게 맞을 수 있다. 사실상 이 세그먼트 트리를 아는지 물어보는 문제기 때문에 더 이상 설명하지 않는다. #include using namespace std; typedef long long ll; struct Edge{ int s, e, l, r; Edge(){} Edge(int s, int e, int l, int r): s(s), e(e), l(l), r(r){} }; struct segTree{ int cnt[2000002], sz[2000002], sum[2000002]; voi..