Mirsky's theorem은 POSET에 관련된 기초적인(?) 정리 중 하나인데, 어디 심층 문제에 대뜸 나왔다길래 포스팅해본다.이에 완전히 대응되는 정리로 Dilworth's theorem이 있지만 증명이 복잡해서 일단은 Mirsky만 증명하기로 한다. POSET(PreOrder SET)의 형식적인 정의는 다음과 같다. 직관적으로는 두 정수 간의 약배수 관계를 생각하면 된다. - 집합 PPP의 원소들에 대해서, 관계 ≼\preccurlyeq≼가 다음을 만족한다.- 반사율 (reflexivity) : 임의의 a∈Pa \in Pa∈P에 대해 a≼aa \preccurlyeq aa≼a.- 추이율 (transitivity) : a,b,c∈Pa, b, c \in Pa,b,c∈P에 대해 \(a \preccurlyeq b \ \w..

문제를 다 푼 사람의 후기는 여기서 볼 수 있다.요즘 실패 후기만 쓰는 것 같아서 기분이 별로다. 서울대랑 카이스트는 잘 봐야지! 문제 요약 : 1. 사골이 되어버린 유형의 확통 문제다. [1-1] A∪B∪C={1,…,6}A \cup B \cup C = \{1, \ldots , 6\}A∪B∪C={1,…,6}이고, ∣A∩B∣=2,∣B∩C∣=1|A \cap B| = 2, |B \cap C| = 1∣A∩B∣=2,∣B∩C∣=1일 때, 가능한 (A,B,C)(A,B,C)(A,B,C)의 개수를 구하여라. [1-2] D∪E={7,8,9}D \cup E = \{7,8,9\}D∪E={7,8,9}이고, ∣D∣>∣E∣≥1|D| > |E| \ge 1∣D∣>∣E∣≥1인 (D,E)(D,E)(D,E)의 개수를 구하여라. 2. 함정에 빠지기 쉽다. 하지만 함정에 빠지지 않는다면 간단히 풀리는 문제다. (난 못풀었다 ㅎ) 다음을 만족하는 [0,1][0,1][0,1]에서 연속인 함수 fff가 존재하는가? f(..

상 탄 주변 블로거 1상 탄 주변 블로거 2상 탄 주변 블로거 3 이 셋 중에 하나는 후기를 올릴 것 같다. 문제 풀이는 저 갓갓들이 올리거나, 아니면 공홈에 빠른 시간 내로 업로드될 것 같으니 대회 문제 풀이가 궁금하다면 저 링크들로. 이 글은 탐레프가 어떻게 고등학교 대회 커리어 마지막 대회를 말아먹었는지에 관한 tmi 꾸러미에 더 가깝다. 대회 문제보다는 대회장 모습, 멘탈의 변화 등을 중심으로 기록한 일종의 일기? D - 1. 예선에 민컷도 나오고, Plane sweeping도 나오고, 작년엔 HLD / 센트로이드도 나왔으니 이번엔 분명 어디서 굴러먹던 근본 없는 고인물 문제가 나올 거라고 예상했다. 그래서 제대로 구현한 적이 없었던 센트로이드, Hopcroft - Karp 이분매칭, Li - C..

대회 링크정신 나간 유사대회...코딩 습관 개선을 위해 후기를 쓰기는 하지만, 절대 추천할 만한 대회는 아니다. A B(+2) C D E1963 -> 2008 (+45) This section is intentionally left blank. Div1A. Cram Time (+, 13min) Tag : Constructive 10910^9109 범위의 두 정수 a,ba,ba,b에 대해서, 1⋯n1\cdots n1⋯n의 정수를 적절히 두 집합으로 분할해서 첫 번째 집합의 합은 aaa, 두 번째 집합의 합은 bbb를 넘지 않도록 해야 한다. 답은 너무 당연히 k(k+1)/2≤a+bk(k+1)/2 \le a + bk(k+1)/2≤a+b인 최대의 kkk일 것 같고, 실제로도 그렇다. 첫 번째 집합에 1,2,⋯m1, 2, \cdots m1,2,⋯m을 쑤셔넣자...

문제 링크 길이 NNN의 수열에 대해서 다음의 쿼리를 QQQ회 수행한다 : - 길이 KKK인 연속한 subsequence를 잡아서 그 중 최솟값을 제거한다. 이 때, 제거된 QQQ개 수들의 (최댓값) - (최솟값)을 최소화하자.Spoiler Alert! tmi 함량이 높은 풀이입니다. O(N2lg⁡N)O(N^2 \lg N)O(N2lgN)으로 풀 수 있고, 에디토리얼에 의하면 N≤105N \le 10^{5}N≤105일 때도 가능하다고 한다.Nlg⁡NN \lg NNlgN이나 Nlg⁡2NN \lg^{2} NNlg2N이겠지만 아직은 모르겠다... 맨 처음엔 대체 어떻게 풀지 싶어서 별 뻘짓을 다했다. 답을 이분탐색하려고 했는데 안되고, 분할정복 같은 걸 끼얹으려고 해도 안되더라. 그러다 문득 답이 결국 aaa의 두 원소의 차이라는 지극히 당연한 사..

PS를 하면서 Persistent라는 단어가 붙는 자료구조는 Persistent Segment Tree 외에는 보기 힘들지만, 사실 Persistent라는 prefix는 꽤나 일반적인 의미를 지닌다. 어떤 자료구조를 계속 업데이트하면서도 이전 버전에 접근할 수 있을 때 그 자료구조를 'Persistent하다'고 한다. 조금 더 세부적으로 분류하면, 이전의 모든 버전에 접근, 수정이 가능하다면 Fully persistent, 이전의 모든 버전에 접근이 가능하지만 최종 상태를 제외하면 모두 read - only라면 Partially persistent 혹은 Confluently persistent라고 한다. 분류는 거창하지만 구현이 그렇게 난해한 건 아니다. 일반적인 방법론은 Fat node, Path co..