본문 바로가기

PS

 (10)
ps일지 오렌지에 도달할 때까지 div.2 D~F 업솔빙한 내용을 기록할 공간입니다. Codeforces Round 1035 (Div. 2)D - Token Removingdp[i][cnt] := [i:n]의 위치에서 cnt개의 수가 제거되도록 a[i:n]을 정하는 경우의 수a[i] 제거 여부를 기준으로 나누면dp[i][cnt] = dp[i + 1][cnt] + dp[i + 1][cnt - 1] * (n - i - (cnt - 1)) * (i + 1)최종답은 sum(dp[0][0:n])
세그트리 메모리 최적화 보통 세그먼트 트리를 구현할 때는 포화 이진 트리 구조를 사용합니다. 이해하기에 직관적이기도 하고, 초기에 작성된 알고리즘 설명글들이 포화 이진 트리를 기준으로 한 것이 크게 영향을 끼치지 않았나 싶습니다.이 경우, 리프노드의 개수는 n보다 크거나 같은 2의 멱수 중 최솟값인 sz로 설정하며, tree배열의 크기는 2*sz가 됩니다.int sz = 1;while (sz 이러한 계산을 생략하고 싶을 때는 tree배열의 크기를 4*n으로 넉넉하게 잡고, sz의 값을 몰라도 되는 top-down방식으로 구현하는 것이 ps에서 일종의 관례가 된 것 같습니다. 하지만 세그먼트 트리를 반드시 모든 레벨이 꽉 찬 포화 이진 트리로 구현할 필요는 없습니다. 불필요한 더미 노드를 제거하고 full binary tree의..
bitset unbounded knapsack $n$개의 수 $x_1, x_2, ..., x_n$ 중 일부의 합이 $k$가 될 수 있는지 판별하는 0/1 knapsack 문제를 bitset으로 최적화하는 방법은 잘 알려져 있습니다.bool knapsack(const vector &v, int n, int k) { vector dp(k + 1); dp[0] = 1; for (auto e : v) { for (int i = k; i >= e; i--) if (dp[i - e]) dp[i] = true; } return dp[k];}// bitset으로 최적화bool knapsack(const vector &v, int n, int k) { bitset dp; dp[0] = 1; for (auto e..
lambda함수 내에서 vector<bool> 사용 시 주의사항 #include using namespace std;int main() { auto check = [&](int x) { vector dp(n + 1, 0); // ~~~코드들~~~ return dp[n]; }; if (check(0)) cout 위 코드는 놀랍게도 UB입니다.애초에 저런 코드를 작성할 일이 있냐? 싶을수도 있지만.. ps에서 parametric search문제를 풀 때 람다함수를 사용하는 경우가 꽤 많죠.. std::vector는 공간 최적화를 위해 일반적인 컨테이너와 다르게 동작합니다. 원래 bool은 1byte지만, vector의 각 요소는 1바이트가 아닌 1비트로 저장됩니다. std::bitset과 같습니다.문제는 이로 인해 특..
시간복잡도 constraintstime complexity$n \le 12$$O(n!)$, $O(n^2 \cdot 2^n)$$n \le 25$$O(2^n)$$n \le 50$$O(2^{n/2})$$n \le 100$$O(n^4)$$n \le 500$$O(n^3)$$n \le 2,000$$O(n^2 \log{n})$, $O(\dfrac{n^3}{16})$$n \le 5,000$$O(n^2)$$n \le 50,000$$O(\dfrac{n^2}{64})$$n \le 100,000$$O(n \sqrt n)$, $O(n \log^2n)$$n \le 1,000,000$$O(n \log n)$$n \le 5,000,000$$O(n \log n)$$n \le 100,000,000$$O(n)$$n \gt 10^8 $$O(\log{..
백준 팁 PS 용어맞왜틀: 분명히 코드를 맞게 짠 것 같으나 틀릴 때 씁니다.TLE: time limit exceeded(시간초과)MLE: memory limit exceeded(메모리 초과)WA: Wrong Answer(틀렸습니다)AC: Accepted(맞았습니다)cp: competitive programming의 약자입니다. 정해진 시간 동안 알고리즘 문제를 해결하는 것으로, ps에 시간 제약이 추가된 것입니다. 백준은 ps에 가깝고, cp는 보통 코드포스에서 연습합니다.그레이, 그린, 민트, 블루, 퍼플, 오렌지, 레드, 누텔라: 코드포스에서의 티어입니다.업솔빙: 대회 중에 못 푼 문제를 대회 종료 후 해설을 보거나 추가로 공부하여 풀어내는 것을 말합니다.UB: Undefined Behavior의 약자입니다..
angular sort auto checkQuadrant = [](const Point &p) -> bool { return p.y 0; else return aq != bq ? aq 실수 오차 때문에 atan2를 사용하기 꺼려지는 경우 ccw로 구현할 수 있습니다.$0 \le \theta \lt \pi$와 $\pi \le \theta \lt 2 \pi$인 경우를 분리해서 생각하면 사이각이 180도 미만일 때만 ccw를 호출하므로 순서가 꼬이지 않습니다.
밀러라빈 using ll = long long;inline ll multiply(ll a, ll b, ll mod) { return __int128(a) * b % mod; }ll power(ll a, ll n, ll mod) { //a ^ n % mod ll res = 1; while (n) { if (n & 1) res = multiply(res, a, mod); a = multiply(a, a, mod); n >>= 1; } return res;}bool isPrime(ll n) { if (n >= 1, ++r; auto check = [&](ll a) { ll remain = power(a, d, n); if (..

티스토리툴바