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 이외에 수열..
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$가 성..
곧 있을 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..
CCO 2022 Day 1을 돌아 만점을 받았다. 2시간 16분 걸렸는데 상당히 쉬운 셋이라는 느낌이 들었다. [BOJ 25220] Rainy Markets (0:50) 일단 해가 존재하는지부터 판별해보자. 각 사람에 대해, 왼쪽 정류장에 가는 경우를 $L$, 우산을 사는 경우를 $M$, 오른쪽 정류장에 가는 경우를 $R$이라고 한다. 왼쪽부터 보면서 최대한 $L$, $M$, $R$ 순으로 그리디하게 배정한다. 자리가 없는 경우 불가능, 아니면 가능이 된다. 이제 해가 존재할 때, $\sum M$을 최소화시키는 방법을 찾아보자. 이번에는 오른쪽부터 보면서, $L$에 있는 사람을 최대한 $R$로 옮기고, 그래도 자리가 남으면 $M$에 있는 사람을 $R$로 옮기고, 그래도 자리가 남으면 $M$에 있는 사람을..