이제 곧 ICPC에 참가해야 하기 때문에 ICPC 입문을 조금 해 보기로 했다. 입문 셋으로 ICPC Seoul Regional 2022를 골랐다. 시간은 딱히 재지 않고 문제를 쉬운 것부터 풀어보았다. J. Parentheses Tree 입력으로 주어지는 괄호 문자열을 파싱하는 문제이다. 스택으로 트리를 만들고 DFS를 돌리는 방법도 있지만 시간이 오래 걸릴 수 있다. 트리를 만드는 과정에서 깊이를 관리하면 상수가 더 작고, 따로 스택을 관리할 필요도 없다(실제 트리의 구조를 만들지 않아도 되므로). 시간 복잡도는 $O(|S|)$이다. F. Frog Jump KOI 2019 중등부 2번 문제에 비슷한 게 있었던 것 같다. 서로 겹치는 구간들의 번호가 인접하기 때문에, 이들을 그룹으로 묶어 준다. 이렇게..
https://www.acmicpc.net/problem/18344 $G=(V, E)$에서 정점 $1$부터 $N$으로 이동하는 최단거리를 찾아야 한다. 단, 이동 중 시작점과 끝점을 포함해 정확히 여덟 개의 서로 다른 정점을 방문해야 한다. 서브태스크 1 (1점) 방문하는 정점을 $[v_1, v_2, v_3, v_4, v_5, v_6, v_7, v_8]$이라고 하고, 이때 사용하는 7개의 간선 번호를 $[e_1, e_2, e_3, e_4, e_5, e_6, e_7]$이라 하자. (단, $v_1 = 1$, $v_8 = N$) $e_2$를 고정하면 $(v_2, v_3)$ 또는 $(v_3, v_2)$가 고정된다. 마찬가지로 $e_4$와 $e_6$을 고정하면 ${ v_4, v_5 }$와 ${ v_6, v_7 }..
KOI 2023 2차 대회 문제들을 풀었다. 초/중/고등부에서 서로 다른 문제는 7개였다. BOJ 28323. 불안정한 수열 어떤 구간 $[l, r]$에 대해 그 안에 있는 수들의 홀짝성이 모두 같다면 이 구간에서는 수를 최대 하나밖에 뽑을 수 있다. 따라서 홀짝성이 같은 인접한 수들은 하나만 남겨도 문제가 없고, 이렇게 합치고 난 뒤 모든 인접한 수들을 고를 수 있고, 이때 남은 수의 개수가 답이 된다. 즉, 첫 수를 고르고, 그 이후로 홀짝성이 바뀔 때마다 고르는 게 최적이다. BOJ 28324. 스케이트 연습 맨 마지막부터 보면서, $i$번 위치에서 속도는 $i+1$번 위치 속도에서 1 늘릴 수 있으면 늘리고, 아니면 최대 제한으로 설정하는 것이 최적이다. 따라서 단순한 순회 한 번으로 $\math..
최근 몇 달 동안 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 Trip JOI 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 Railw www.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..