취미로PS하는사람

https://www.acmicpc.net/problem/4149 큰 수를 소인수분해 해보자. 우선 밀러-라빈 알고리즘으로 해당 숫자가 소수인지 판별한 후 폴라드-로 알고리즘으로 소인수분해 하면 된다. 밀러-라빈 알고리즘은 검사하는 소수의 개수를 $k$, 소인수분해 하려는 수를 $n$이라 할 때 시간복잡도가 $O(k \log^3 {n})$이다. 자세한 사항은 위키백과를 참고하자. 참고로 $2^{64}$까지의 숫자를 결정론적으로 검사할 때는 $p = 2, 3, 5, ..., 37$이면 충분하다. 폴라드-로 알고리즘은 어떤 난수 발생 함수(이를테면 $f(x)=(x^2+1)\mod n$)가 $\mod n$에 대해 반복됨을 이용하는 것인데, 그 반복되는 주기가 $n$의 약수임을 이용한다. 자세한 내용은 나도 잘..

https://www.acmicpc.net/problem/3121 그 테크닉을 배웠다. (2022.1.5 추가: rotating sweep line 이라고 부르는 것 같다.) $N$개의 점이 있을 때, 특정 기울기의 법선 벡터를 가지는 직선에 점들을 정사영하여 그 순서를 알고 싶다. 만약 Naive하게 구현한다면 각도는 최대 $O(N^2)$개, 점들의 정렬에 대략 $O(Nlog{N})$이 소요될 것이므로 시간이 너무 오래 걸린다. 하지만 잘 생각해보면 정렬된 상태는 법선벡터와 어떤 두 점을 잇는 직선의 기울기가 동일해질 때 그 두 점의 위치만 인접한 상태에서 바뀌기 때문에, 점 쌍들을 기울기로 정렬하여 순서대로 두 점의 위치만 바꾸어주면 모든 $N^2$개의 각도에서 정사영한 순서를 알 수 있다. 각도 정..

https://oj.uz/problems/source/67 1. gondola 코딩 노가다 문제. 3번을 제일 빨리 짠 것 같다.... 어째 가면 갈수록 쉬운 문제를 더 못 푸는 것 같다. 코포 포함 아무튼 문제는 간단하다. 곤돌라 수열은 그냥 1, 2, ... , n인 수열을 회전시킨 수열이다. 그런데 대신 원소를 하나씩 뽑아 n+1, n+2, ... 로 대체할 수 있는 것이다. 1번 문제는 해당 수열이 곤돌라 수열인지 확인하는 문제로, n이하인 숫자 사이의 순서 관계와 중복 원소에 대한 것만 잘 처리해주면 된다. 중복원소 처리를 안 한 상태로 모두 n보다 클 경우 바로 1을 리턴하는 실수를 저질러 시간을 많이 뺏겼다... 2번은 해당 곤돌라 수열을 만드는 방법에 대해 알아내는 것이다. 이 역시 n보다..

https://oj.uz/problems/source/379 1. Cake 3 유사 holiday (IOI 2014) 이다. 잘 생각해보면 결국 M개의 케이크조각을 골랐을 때 ∑|C_i-C_i+1|은 2 * (MAX(C_i) - MIN(C_i)) 와 같다는 것을 알 수 있다. 우선 케이크조각을 원형으로 배치한다 했을 때 제일 작은 원소와 큰 원소를 먼저 놓고, 나머지를 끼어넣는다 생각하자. 그러면 결국 최적해는 가장 작은 원소에서 가장 큰 원소로 갈 때 C가 증가해야한다는 것을 알 수 있다. 이 때 총 비용은 2 * (MAX(C_i) - MIN(C_i))이 된다. 그러면 이제 문제는 적당히 M개를 골라서 V를 모두 더하고 거기서 2*(MAX(C_i)-MIN(C_i))를 뺀 값의 최댓값을 구하면 된다. 우..

https://oj.uz/problems/source/65 rail은 귀찮아서 풀이를 보지 않았다. 1. rail 끝까지 못 풀었다. 서브태스크 2까지 풀었는데, 0번 역에서 가장 가까운 역은 0번 역에서 D타입 중에 가장 오른쪽 역이니까 이 역의 타입과 위치를 구할 수 있다. 이 역에서 또한 모든 역까지의 거리를 구한 뒤 0번 역에서 어떤 역으로 가는 비용이 0번에서 방금 구한 역까지의 거리와 방금 구한 역에서 어떤 역까지의 거리를 더한 것과 같다면 C 타입이므로 위치와 타입 모두 알 수 있다. 코드 더보기 #include "rail.h" #include #define fi first #define se second #define eb emplace_back #define em emplace #defi..