본문 바로가기

알고리즘225

cf 596 div2 D - Power products (소인수분해, 수학) https://codeforces.com/contest/1247/problem/D 최대 1e5의 크기가 n인 배열 a가 주어진다. 임의의 자연수 x에 대해 ai * aj = x^k를 만족하는 쌍의 개수를 구하라. 0~i-1번 중 i번과 쌍을 이루는~ ai를 소인수분해해서 (j번째로 작은 소수가 나온 횟수 % k)값을 적절히 벡터(v)에 담으면, 0~i-1번의 벡터 중 v와 쌍을 이루는 벡터의 모양은 하나로 정해진다. map로 그값을 유지하여 계산해 나간다. 1e5이하 소수는 10000개정도 되니까 위 방법을 그대로 적용하려면 시공간복잡도가 너무 크다. 제곱근1e5 이하의 소수를 smallprimes라 하고 그 외 소수를 bigprime이라고 하자. a는 최대 1e5이므로 제곱근1e5보다 큰 소수(bigp.. 2020. 3. 15.
cf 562 div2 C - Increasing by modulo (이분탐색, 그리디) https://codeforces.com/contest/1169/problem/C 0~m사이 값을 갖는 n개의 요소를 갖는 배열이 주어진다. 임의의 배열 요소을 여러개 골라 (ai+1) % m해주는 것을 하나의 operation이라 할때, 배열 a를 단조증가로 만들기 위해선 최소 몇번의 operation을 해야 하는가? 최소 0번 최대 m번의 operation이 필요하다. 어떤횟수 이상의 operation을 수행하면 정렬이되므로 이분탐색. bool pos(k) : k번 operation으로 a 정렬 가능? for(int i=0; i k) return false; b[i] = p; } else { if (m - b[i] + p > n >> m; a.resize(n); for (int i = 0; i < n.. 2020. 3. 15.
cf 626 div2 D - present (수론, 이분탐색) https://codeforces.com/contest/1323/problem/D 어렵지만 여기저기서 출제된 적이 있는 문제. 핵심 아이디어는 가져가자 최대 4e5개의 원소 n개를 갖는 배열이 있다. 원소는 1e7이하의 자연수를 갖는다. n개 중 2개 원소의 가능한 모든 쌍에 대해 합을 구해 모두 xor한 값을 구해라 (a1+a2)⊕(a1+a3)⊕ … ⊕(a1+an)⊕(a2+a3)⊕ … ⊕(a2+an)…⊕(an−1+an) 한 쌍의 합의 최댓값은 2e7이므로 답을 ans라 했을때 ans는 24개 비트로 표현 가능하다. ans의 k번째 비트가 켜져있는지 nlogn에 알 수 있다. a의 원소들은 k+1번 이후의 비트는 k번째 비트에 영향을 주지 않는다. b 2020. 3. 15.
cf 564 div2 D - Nauuo and circle (tree, graph dp) https://codeforces.com/contest/1173/problem/D 정확하지 않은 잘못된 점화식을 쓰려다 실패 최대 2e5의 정점 n개를 갖는 트리가 주어진다. 정점을 원위에 일정한 간격으로 배치했을 때 간선이 교차하지 않는 경우의 수를 구하라. n=4, edge = {(1,2), (1,3), (2,4)}인 경우 8. 아래 그림 참조 원의 맨 위를 1로 고정(전체드리의 루트 고정)시킨 후 경우의수를 구해서 마지막에 n을 곱하자 f(u) : u를 루트로하는 서브트리를 간선이 교차하지 않도록 배치하는 경우의 수 (각각의 자식노드를 루트로 하는 서브트리(sub(v))를 비어있는 원 위에 순서대로 배치하면 된다. 이 때, 각각의 칸 안에도 sub(v)의 루트와 그 자식들이 순서대로 배치돼야 한다... 2020. 3. 15.

티스토리툴바