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

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

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

문제 링크 \(1 \le N \le 18\)에 대해 길이 \(2^{N}\)의 정수 배열이 주어진다. (0 - based) 이 때, 모든 \(1 \le K \le 2^{N}-1\)에 대해 다음을 구하라. \(|\)는 bitwise-or이다. $$ \max_{i < j, \ i \ | \ j \le K} \left(A_{i} + A_{j}\right) $$Spoiler Alert! \(i | j \le K\)는 도저히 답이 안 나온다. 다행히 \(i | j\)의 모든 비트가 \(K\)의 비트에 포함되는 경우만 고려해도 충분하다. K-1일 때의 답과 max를 취해주면 되니까. 모든 i에 대해서 다음과 같은 f(i)가 있으면 좋을 것 같다 : f(i) : i에 포함되는 비트를 가진 인덱스(Bit - Subset..

수올문제 자료집을 돌다가 그나마 풀만한 문제들이 보여서 풀어보았다. 나한테 풀리는 걸 보면 그렇게 변별력이 있는 문제들은 아니거나, 사풀 유도가 굉장히 악랄하거나. 1, 2, 3, 4-(a)를 풀었고, 4-(b)는 아직 푸는 중이다. 문제 링크(한국어) Spoiler Alert! This section is intentionally left blank.1. 다음을 만족하는 \(f : \mathbb{Q}^{+} \to \mathbb{N}\)을 모두 구하여라. $$ \forall x, y \in \mathbb{Q}^{+}, \quad f(xy) \cdot \gcd \left( f(x)f(y), f(\frac{1}{x})f(\frac{1}{y}) \right) = xyf(\frac{1}{x})f(\frac{1..

처음으로 AC를 받은 ARC E번!ARC099E. Independence Independence는 PS에서 흔치 않게 완전그래프가 등장하는 문제다. 하나만 포스팅하기 아까워서, 역시 완전그래프가 등장하는 POI문제 2개를 추가로 포스팅하기로 했다. 세 문제의 관찰이 모두 다르다. POI11. PartyPOI11. Conspiracy 여담이지만 Party는 Stage 3-2고 Conspiracy는 Stage 1-1데 Conspiracy가 훨씬 어렵다. 도대체 그들의 스테이지 선정 기준은... Intro) POI11. Party Tag : Complete graph, Naive(...) 크기 \(n\) (3의 배수)인 그래프가 주어지는데, 최소한 \(\frac{2}{3}n\) 크기의 clique가 있다는 것..