pseong

제곱수로 나누어 떨어지는 경우 이미 처리해 줬기 때문에 제곱수로 안 나누어 떨어지는 경우에 대해서만 포함 배제의 원리를 사용해야 한다. 제곱수로 나누어 떨어지는 경우는 전부 계산에서 제외해 주었기 때문에 어떤 수의 소인수들은 전부 한개만 가지고 있다. 먼저 x까지의 모든 숫자의 개수는 x개이다. 소수인수가 홀수개로 이루어져 있다면 빼주면 되고 짝수개로 이루어져 있다면 더해주면 된다. 1557번: 제곱 ㄴㄴ 어떤수 N이 1이 아닌 제곱수로 나누어지지 않을 때, 이 수를 제곱ㄴㄴ수라고 한다. 제곱수는 4, 9, 16, 25와 같은 것이고, 제곱ㄴㄴ수는 1, 2, 3, 5, 6, 7, 10, 11, 13, ...과 같은 수이다. K가 주어졌을 때, K www.acmicpc.net

Problem - D - Codeforces codeforces.com 어떤 배열이 존재하는데 칸막이 두 개를 설치해서 나눠진 3개의 그룹의 각각의 합보다 큰 최소의 2의 거듭제곱의 차의 합을 최소로 만드는 문제이다. 그냥 나이브하게 생각하면 O(N^2) 이 걸리기 때문에 나이브하게는 안된다. 그래서 그냥 직관적으로 한 개의 칸막이는 처음부터 끝까지 순서대로 확인하면서 두 번째 칸막이가 2의 거듭제곱보다는 같거나 작지만 가장 큰 수가 중간 구간에 만들어지게 움직이면 될 거라고 생각했다. 그래서 그렇게 풀었더니 AC가 나왔다. 근데 이게 최적의 해인지 자명한가? 를 따져보는데 뭔가 쉽게 자명하다는 게 증명이 안됐다. 그렇게 생각의 함정에 엄청난 시간을 소비했고 소비하고 난 후 더좋은 풀이도 떠올라서 글로 ..

제 1종 스털링 수 모든 노드의 outdegree가 1이고 indegree도 1인 노드가 n개인 그래프에서 k개의 사이클이 생기는 경우의 수를 의미한다. 이 그래프는 일대일 대응이므로 간선은 전단사 함수라고 할 수 있다. s(n,k) = s(n−1, k−1) + (n−1)s(n−1, k) 어떤 한 노드를 self loop라고 했을 때 n-1개에서 k-1개의 사이클이 생기는 경우의 수는 s(n-1, k-1) 이다. 어떤 한 노드를 제외하고 n-1개에서 k개의 사이클이 생기는 경우의 수는 s(n-1, k) 이고 어떤 한 노드를 이제 이미 만들어진 k개의 사이클로 넣어야 한다. 이 경우 어떤 한 노드의 친구를 정해고 그 친구와 함께 사이클에 들어간다고 하면 친구를 만드는 경우의 수는 n-1개이고 따라서 (n-..

Problem - D - Codeforces codeforces.com D 치곤 너무 문제가 말도 안 되게 어렵고 이 문제를 풀어야 오렌지 퍼포먼스라니 글로벌 라운드라 그런가? 아무튼 여태 푼 D번중에 가장 어려운 문제였다. 정수론에 약한 면이 있어서 그럴 수도 있겠지만 개인적으로는 그렇다. 어떤 수열 c를 c1, c2, c3, ... 인 ci라고 하자. 수열 c가 good 인 상태를 판별하기 위해서 먼저 각 시퀀스 ci의 첫 시작을 0이라고 하자. 그렇게 되면 각 시퀀스의 총합은 ci(ci-1)/2 가 되고 각 시퀀스의 총합을 더한 전체 총합 s = ∑ci(ci-1)/2 가 된다. 여기서 s를 0으로 만들 수 있다면 good인 상태가 된다. 각 시퀀스의 총합은 시퀀스를 이루고 있는 개수만큼 총합이 움직..

Problem - E - Codeforces codeforces.com k가 최대 20개 까지니까 고정할 메시지를 개수를 1부터 20개 중 최적의 하나를 선택하여 구성하면 된다. 고정할 메시지 개수를 t 개라고 하자. 이때 모든 메시지 번호에 기댓값을 부여할 수 있다. 메시지 번호를 기댓값 대로 정렬해 준 다음 큰 순서대로 메시지 t개를 선택한다. 그렇게 되면 고정할 메시지 개수 t개에 따른 전체 기댓값이 나오게 된다. 어떤 메시지 번호 x가 고정할 메시지 개수 t에 포함한다고 가정하자. 메시지 번호 x의 기댓값은 메시지 번호 x를 원하는 사람 i의 min(t, k[i]) 의 모든 합이다. 만약 k[i] 가 t개보다 작다면 메시지 x를 선택할 확률은 k[i] / t이다. 만약 k[i] 가 t개보다 크다면..

Problem - D - Codeforces codeforces.com a와 b가 주어지고 |a-b| 를 a 또는 b로 계속 교체하는데 도중에 x가 등장하는지 판단하는 문제다. 일단 |a-b| 를 a와 b 중 큰 수와 교체를 해야 한다. 작은 수와 교체를 해 보면 숫자가 계속 반복된 다는 것을 알 수 있다. 결국 a b 중 큰 수와 |a-b|를 계속 교체해야 한다는 것을 알 수 있다. 하지만 일일이 교체하다 보면 시간이 너무 오래 걸린다. 교체를 건너뛸 수 있는 경우가 존재한다. a b 중 b 가 a보다 100배 이상 큰 수라고 가정하자 그러면 b는 계속 b-a로 교체가 될 것이고 이는 b에서 계속 a를 빼는 결과와 같다. b가 a보다 작아질 때까지 b에서 a를 빼므로 도중에 x가 나오는지 판별할 때는 ..

Problem - D - Codeforces codeforces.com 먼저 전체 구간에 대한 쿼리를 날려서 전체 개수를 얻는다. 그리고 이분 탐색으로 쿼리를 날려서 i j k에서 i를 찾는다. 그리고 i+1 부터 n까지 쿼리를 날려서 전체 개수에서 얼마만큼 빠졌는지 구하면 j 위치를 알 수 있다. 그렇게 되면 k위치는 x*(x-1)/2 = k-j+1 가 되는 x값을 이분 탐색으로 찾으면 k가 구해진다. 총쿼리의 개수는 1 + logn + 1 이므로 최대 32개이다.

Problem - D2 - Codeforces codeforces.com 그래프 그리디 문제인데 굉장히 관찰이 어렵다. 가장 멀리서 쿼리를 날려야 거리가 중복되는 노드들이 가장 작아지므로 먼저 리프 노드를 쿼리로 날려야 한다는 것을 알 수 있다. 따라서 간단하게 모든 리프 노드를 전부 쿼리를 날리면 찾고자 하는 노드 x를 알 수 있을 것이다. 하지만 우리는 쿼리의 개수를 줄여야만 한다. 어떤 한 노드 y 기준으로 차수가 k라고 하자. 그 노드 y에 인접한 노드가 찾고자 하는 노드 x라고 한다면 그 노드 y의 서브 트리 (차수)를 k라고 한다면 굳이 k개의 서브 트리에서 쿼리 노드가 다 있을 필요는 없고 k개의 서브 트리에서 1개를 뺀 k-1개의 서브 트리에서만 쿼리 노드가 있으면 된다. 여기서 쿼리 노드..