dlwocks31의 PS일기장

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..

RTG3A로 만난 문제이다. 풀이 모든 가능한 subsequence를 다 보는 가장 간단한 브루트포스는 \(O(n\cdot 2^n)\)이다. 팀연습 중엔 여기까지밖에 생각을 못했고, 에디토리얼을 보고 내가 이해하기 편한 식으로 풀이를 한번 풀어서 써보았다. 우선 아래의 토의를 위해 \(a_i\)의 비트 개수를 \(m\)이라 하자. 즉, 이 문제에서는 \(m = 20\). 먼저 \(a_i = 0 \text{ or } 1\)인 케이스를 생각해보자. 즉 \(a\)는 bitstring of length n. 이 상황에서 bitwise and가 0이 되는 경우의 수를 찾을려면, 먼저 0인 숫자가 하나라도 subsequence에 들어가면 bitwise and는 0이 된다는 것을 생각해보자. \(a\)에 1이 \(t..