문제 링크 길이 \(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\)의 두 원소의 차이라는 지극히 당연한 사..

문제 링크 \(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..

처음으로 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가 있다는 것..

편 ㅡ 안 이번에 푼 문제 (4 / Total 20) #기존에 풀어둔 ARC문제를 이번에 포함시킴 포스팅하는 문제만 볼드. ARC099D Snuke numbersARC097D EqualsARC095D Binomial CoefficientsARC093D Grid Components 고민중인 문제 ARC099E. Independence ARC101E. Ribbons on Tree ARC099D. Snuke Numbers 자릿수합 함수 \(S(n)\)에 대해서, \(\forall m > n \frac{m}{S(m)} < \frac{n}{S(n)}\)을 만족시키는 \(n\)을 Snuke number라고 한다. 최소 \(K\)개의 Snuke Number를 찾아야 하고, \(K\)번째 Snuke Number가 \(..

ARC는 언제나 어렵다ㅏㅏㅏ오늘만 푼 문제는 아니고, #001을 올린 뒤부터 풀어낸 문제들. 1편 링크 이번에 푼 문제 (5 / Total 11) ARC097C K-th substringARC094C Same IntegersARC093C Traveling PlanARC101D Equal Cut #Editorial 봄... 근데 생각해 낸 풀이랑 같았다. 증명해볼걸ㅠARC094D Worst Case #맞왜틀 끝에 Editorial 봄. (180919 21:15 추가) 고민중인 문제 : ARC099D Snuke Number #Editorial 아직도 이해 못함ARC097D EqualsARC095D Binomial Coefficient ARC094C. Same Integers 50 이하의 세 정수 A, B, ..

너무 많이 쉬었더니 PS실력이 집을 나가버렸다.ko_osaga님의 추천으로 ARC를 최근 것부터 밀어보기로 했다. EF는 어려우니까 CD부터. 물론 D마저도 몇 개 못 풀었다... 은퇴를 고려해야 하나. C는 대부분 간단한 관찰로 밀어버릴 수 있는 문제같다. 코드도 400B 안쪽으로 나오는 것 같으니 웬만큼 좋은 문제가 아니면 포스팅하지 않을 계획. 오늘 푼 문제(6 / Total 6) : ARC102C (Triangular Relationship)ARC102D (All Your Paths are Different Length)ARC101D (Median of Medians) #오늘 푼 문제는 아닌데 괜찮은 문제라서 포스팅.ARC100C (Linear Approximation)ARC098C (Attent..