본문 바로가기

알고리즘225

Codeforces #627 div3 F - Maximum white subtree (graph dp, reroot) https://codeforces.com/contest/1324/problem/F reroot 첫 성공 무방향트리가 주어진다. 각 정점마다 하얀색(1)또는 검은색(0)으로 색칠되어 있다. i번 정점을 포함하는 서브트리 중 하얀색정점의 개수 - 검은색 정점의 개수가 최대인 경우 그 값을 각각 구해라 (i=1,2,3,4...n) 1번 정점을 root로 하는 전체 트리에서 dp[u] : u를 포함한 서브트리에서 cntw-cntb 최대값 u에 인접한 v에 대해 ans[v] = dp[v] + max(dp[u],0)이다. v에서원하는 값 ans[v]가 u,v에대한 상태로만 정의되므로 reroot 적용가능하다. dp[u] -= max(dp[v],0) dp[v] += max(dp[u],0) go(u,v) dp[u] =.. 2020. 3. 14.
Educational #56 D - GCD counting (트리(숲) 지름, 소인수분해) https://codeforces.com/contest/1101/problem/D 소인수분해 시간복잡도를 잘못 파악하고 있었다. 루트n인줄 알았는데 소인수분해는 loglogn이다. (에라토스가 루트n이다) 트리 지름 구하는 방법은 알고 있었지만 숲에서 최대 지름을 구하는 것을 O(n)에 할 방법을 생각하지 못했다. 같은 시간복잡도를 갖는 코드라도 시간제한이 빡빡해서 최적화를 해줘야 한다. (난이도에 비해 푼 사람이 적은 이유인듯) 단일 트리와 다른 특별한 알고리즘을 사용하진 않는다. 한 점 잡고 제일 먼 점 u와 u에서 제일 먼 점 v와의 거리를 모든 트리에 대해 구하면 된다. 하나의 트리에 대해 최대 지름을 구한 후, 방문처리를 위한 vst배열을 초기화하지 않고 다음 트리에 대해 최대 지름을 구하는 부.. 2020. 3. 13.
BOJ 11510 - TOPOVI (constructive, greedy) https://www.acmicpc.net/problem/11510 시공간복잡도 파악이 힘들어서 풀이방법 자체가 떠오르지 않았다. 최대 1e9*1e9 정사각형 모양의 한 변의 길이가 n인 그리드위에 룩(rook)을 배치할 것이다. 모든 룩은 1e9 이하의 power를 부여받는다. power가 x인 룩이 (r,c)에 배치된다면, r번 row의 모든 칸의 값에 x를 XOR한 값을 저장한다. c번 column도 마찬가지다. (따라서 칸(r,c)는 두 번 xor되므로 칸(r,c)에 저장된 값은 변하지않는다.) 초기에 최대 1e5개의 룩 k개를 배치한다. (r,c,x) 이후에 최대 1e5번 (r1,c1)에 위치한 룩을 모두 (r2,c2)에 이동시킨다. (r1,c1,r2,c2 ,, 꼭 (r1,c1)에 룩이 있다는 .. 2020. 3. 11.
조합의 소수 모듈러 값 빠르게 구하기 (n C m % p) https://ryulstory.tistory.com/62 페르마 소정리에 따르면 p가 소수인 경우 a^(p-1) = 1 (mod p) 1/a mod p == a^(p-2) 즉 다음을 만족함 (a*b) % p = (a%p) * (b%p) (a/b) % p = (a%p) * (b^(p-2) % p) nCk (mod p) = n! /(k! * (n-k)!) (mod p) = (n! mod p) * ((k! * (n-k)!)^(p-2) mod p ) 다음 두 배열을 전처리해준다. O(n) fac[x] : x! % MOD fac_inv[x] : (x!)^(-1) %MOD -> n * inverse(n!) = inverse((n-1)!) 를 이욯 O(1)에 nCm % p 를 구할 수 있다. const ll MOD.. 2020. 3. 10.

티스토리툴바