요즘 애드혹 감각이 좀 줄어든 것 같아서 백준에서 플래-다이아 애드혹 문제들을 랜덤하게 10개 뽑아 풀어 보았다. 괜찮은 문제도 있었던 반면 풀기 싫은 문제도 많이 있었다. 1. ? 정말 풀기 싫은 문제가 뽑혀서 안 풀고 넘어갔다. 무슨 문제였는지는 공개하지 않는다. 2. Монотонная подпоследовательность 길이가 $n$인 순열 중 LIS나 LDS의 길이 최댓값이 $k$인 것을 찾는 문제이다. Erdos-Szekeres Theorem에 의하면 길이가 $(r-1)(s-1)+1$ 이상인 수열은 길이 $r$의 증가부분수열이나 길이 $s$의 감소부분수열이 있다. $r=s=k+1$을 넣으면, $k^2+1$ 이상의 길이를 가진 수열은 길이 $k+1$ 이상의 IS/DS가 있다. 따라서 $n >..
BOJ 15481. 그래프와 MST 일단 원래 그래프의 MST를 구한다. 그리고 각 간선에 대해, 해당 간선의 양끝점을 잇는 경로에서 가장 큰 가중치를 가지는 간선을 빼 주고 해당 간선을 넣으면 이것이 가장 싼 MST가 된다. 구현은 LCA와 sparse table을 잘 이용하면 HLD + segment tree 없이도 할 수 있다. 시간 복잡도는 $\mathcal{O}(M \log N)$이다. BOJ 30896. 두 팀으로 나누기 두 팀의 $\min(A_i)$와 $\sum B_i$를 각각 $a_1$과 $a_2$, $b_1$과 $b_2$라고 하자. $a_1$과 $a_2$ 중 하나는 $\min_{1 \le i \le N} A_i$이다. WLOG $a_1$이라고 하자. $a_2$를 정하는 방법은 최대 $10..
친구들과 함께 연습셋을 돌았다. 그 중 다이아 이상 문제 몇 개에 대해 간단히 정리해 둔다. BOJ 8473. Monopoly 좌표평면에 $N$개의 점이 주어질 때, 택시 거리가 $c$ 이하인 점들을 간선으로 연결하자. 연결 성분의 개수와 가장 큰 연결성분의 크기를 구하면 된다. 일단 좌표평면을 45도 회전해 생각하면 택시 거리는 체비셰프 거리 $\max(\Delta x, \Delta y)$ 가 된다. 이렇게 변형하면 한 점과 간선으로 직접 연결될 수 있는 점의 영역을 가로/세로 $2c$인 정사각형으로 생각할 수 있다. 이제 이러한 영역 안의 점을 빠르게 찾을 수 있는 방법을 생각해 보자. 위의 좌표 변환을 통해 다음처럼 문제를 변형할 수 있다. 각 점 $(a, b)$가 있고, $x$ 범위가 $[a-c,..
제목만 들어도 모두가 아는 이 전설의 문제는 ONTAK 2010에 출제된 문제다. ONTAK은 폴란드 국가대표 선발 캠프라고 알고 있는데, 자세한 내용은 찾아도 잘 안 나와서 딱히 깊이 알고 있지는 않다. 문제는 단순하다. 10개의 파일이 있고, 정수 하나를 입력받아 $(0 \le N \le 10)$ 그저 대응되는 파일의 내용을 출력하기만 하면 된다. 단 코드의 길이는 10만 바이트를 넘을 수 없고, 출력 파일은 예제 파일 $(N = 0)$을 제외하고 모두 20만 바이트를 가뿐히 넘는다는 게 특징. gen0.out 그냥 출력하면 된다. gen1.out 파일이 너무 커서 웬만한 프로그램으로 열려고 해도 열기 힘들다. 경험상 Visual Studio Code가 이럴 때 정말 좋은 역할을 해 준다. 파일을 열..
이제 곧 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 이외에 수열..