본문 바로가기

알고리즘/코드포스44

Educational 84 div2 D - Infinite Path (약수, 수론, 후속노드그래프) https://codeforces.com/contest/1327/problem/D 약수를 모두 구하는 건 O(루트n), 전처리 후 O(n^(1/3)) 소인수분해는 필요 없다. 사이클 덩어리들이 주어진다. 사이클에 포함된 u,v에 대해 u->v면 v->u경로가 반드시 있다.(주어진 p 배열이 순열이므로) 번호마다 색이 주어진다. 사이클에서 k번째 후속노드를 가리키는 그래프가 모두 같은 색을 이룰 때 infinite path를 이룬다고 하자. infinite path가 존재하기 위한 k의 최소값을 구해라. 사이클의 크기의 1이아닌 약수 k번째 후속노드를 가리키는 그래프는 쪼개진다. 그 외의 경우 사이클의 순서는 바뀔 수 있지만 구성요소는 바뀌지 않는다. 사이클마다 약수번째 후속노드를 가리키는 그래프가 inf.. 2020. 3. 24.
global round #7 D2 - Prefix-Suffix Palindrome (실패함수, prefix function) https://codeforces.com/contest/1326/problem/D2 문자열 s가 주어질 때, s의 prefix a, suffix b를 이어붙여 만들 수 있는 최대길이 팰린드롬을 출력하라. (단, a+b 0 && t[i] != t[j]) j = pref[j - 1]; if (t[i] == t[j]) pref[i] = ++j; } int tt; string inp; string prefixPalin(string a) { string b = a; reverse(b.begin(), b.end()); string s = a + "#" + b;//더미문자 추가해서 s길이 홀수로 강제 vector pref(s.size()); int j = 0; for (int i = 1; i < s.size(); i.. 2020. 3. 20.
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.

티스토리툴바