요즘 애드혹 감각이 좀 줄어든 것 같아서 백준에서 플래-다이아 애드혹 문제들을 랜덤하게 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..
tl;dr 글이 너무 길어서 읽기 귀찮다면 결론만이라도 읽자. 개요 요즘 커뮤니티 대회에 관해 말이 많다. 최근 여러 대회에서 대회 이후에 문제 오류가 발견되는 상황이 있었고, 현재의 대회 검수 시스템에 대한 전반적인 재정비의 필요성이 시사된 바 있다. 나 역시 현재의 검수 시스템에 문제가 있음에 동감하는 바이지만, 이 글에서 이야기하고자 하는 바는 아니다. 이 글에서 이야기하고자 하는 것은 문제의 질에 관한 것이다. 조금 민감한 주제일 수 있다는 것을 인지하고 있고, 이 글에 적힌 건 어디까지나 내 의견일 뿐, 절대적인 것이 아님을 전제로 읽어주셨으면 한다. (비고: 글을 올리기 전 몇몇 사람들에게 피드백을 받은 결과, "좋은 문제"의 의미가 조금 모호하다는 이야기를 들었다. 내가 이 글에서 이야기하고..
친구들과 함께 연습셋을 돌았다. 그 중 다이아 이상 문제 몇 개에 대해 간단히 정리해 둔다. 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 }..