요즘 애드혹 감각이 좀 줄어든 것 같아서 백준에서 플래-다이아 애드혹 문제들을 랜덤하게 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..
제목만 들어도 모두가 아는 이 전설의 문제는 ONTAK 2010에 출제된 문제다. ONTAK은 폴란드 국가대표 선발 캠프라고 알고 있는데, 자세한 내용은 찾아도 잘 안 나와서 딱히 깊이 알고 있지는 않다. 문제는 단순하다. 10개의 파일이 있고, 정수 하나를 입력받아 $(0 \le N \le 10)$ 그저 대응되는 파일의 내용을 출력하기만 하면 된다. 단 코드의 길이는 10만 바이트를 넘을 수 없고, 출력 파일은 예제 파일 $(N = 0)$을 제외하고 모두 20만 바이트를 가뿐히 넘는다는 게 특징. gen0.out 그냥 출력하면 된다. gen1.out 파일이 너무 커서 웬만한 프로그램으로 열려고 해도 열기 힘들다. 경험상 Visual Studio Code가 이럴 때 정말 좋은 역할을 해 준다. 파일을 열..