dlwocks31의 PS일기장

https://codeforces.com/contest/1198/standings/participant/26799422#p26799422 A - array의 distinct value한테만 비트를 배정해야 한다는 걸 못봐서 한번, 바이너리서치하는 배열을 정렬 안해서(..) 한번 틀리고 그걸 발견 못해서 B 풀고 와서 좀 더 직관적인 좌표압축? 코드를 짜서 맞았다. B - 온라인으로 풀면 레이지 세그를 써서 2번 쿼리를 레이지하게 뿌리면 된다. Div1B에겐 오버킬이였고, 정해는 오프라인으로 1번 쿼리들마다 앞으로 올 2번 쿼리의 값의 최댓값으로 바꿔쓰는 식. 너무 복잡하게 생각한 듯 하다. 나중의 2번 쿼리가 앞에 있는 어떠한 1번 쿼리든지 덮어씌울 수 있는 포텐셜이 있다! 식으로 접근하면 이런 풀이에 ..

https://codeforces.com/contest/1197/standings/participant/26546079#p26546079 일단 오렌지 복귀는 했으니 잘한걸로..? A. DIY Wooden Ladder 가장 큰 두개를 수직선으로 삼으면 된다. B. Pillars max에서 시작해서 투포인터로 퍼저나가는 방법을 썼다. maximum이 global maximum인지 확인하는 방법이 더 좋고 편한 방법같다. n-1을 찾고 - n-2를 찾고 - ...식으로 생각해서 이런 풀이가 나왔던거 같다. 쉬운 문제여서 다행히 큰 상관은 없었다. C. Array Splitting 처음에 a_i >= a_i-1를 못보고 whining하고있었다. 조건을 잘 읽자.. division하는 operation이 cost..

https://codeforces.com/contest/1178/standings/participant/26499798#p26499798 결과적으로는 만족스러운 라운드였다. :) A. Prime Minister 그리디하게 가져올 수 있는 파티를 다 가져오면 된다. A번치고 문제가 길어서 읽기 힘들었다. B. WOW Factor o하나당 (좌측에 있는 w개수*우측에 있는 w개수)를 더하면 되고 왼쪽에서 오른쪽으로 순차적으로 보며 카운트를 잘 관리하는 식으로 O(n)에 풀 수 있다. C. Tiles 대회 중에는 처음에는 dp쪽으로 생각해보다가, 예제를 보고 2**(w+h)라는 식을 찍어서 냈고 맞았다.이 식이 맞다고 확신한 결정적 계기는 14분여쯤에 맞은 사람 수를 봤는데 200명이 좀 넘었다. 정말 dp였..

RTG3 C 로 만난 문제이다. 시도 처음 봤을 때는 n이 작으니 어떻게든 모든 가능한 트리를 다 순회해보면 되지 않을까? 하는 생각이 들었다. 모든 가능한 parent assginment를 다 시도해보면 \((n-1)^{n-1}\)이라 안되고, 트리에 dfs in/out기록을 토대로 만들 수 있는 2n짜리 bracket sequence? 같은걸 순회해볼 생각도 했다. 이건 \( n\cdot 2^{2n-2} \) 정도의 비벼볼만한 시간복잡도가 나오는데 이렇게 카운트하면 children의 순서가 바뀌면 다른 트리로 카운트된다는 것을 깨닫고 그 중복을 없애볼 생각을 하다가 너무 어려워서 포기했다. 풀이과정 우선 풀이의 첫 몇줄에서 (\(dp_{i, bm}\) = i를 루트로 하고 bm(bitmask의 약자)..