목록Algorithm (121)
블로그 옮겼습니다
이건 확실한건아니고 들은 사실인데 모듈러를 많이하면 생각보다 속도 저하가 있다고한다. 그래서 코포에서 고수들도모듈러 연산을 줄이는 테크닉을 많이 쓴다고 들었는데 ans 를 구할 때 어떤 여러개의 답들을 곱해서 모듈러연산을 한거라면 못쓰고..더해서 구할땐 쓸 수가 있는데 더하는 것들이 둘다 mod 미만이라는 것이 보장되기 때문에아무리 더해봤자 2*mod 미만일 것이다. 그렇기 때문에ans %= mod 를 하는대신while(ans>mod)ans-=mod; 를 하면 while 문이 한번만 돌기 때문에 모듈러를 하는 대신 - 연산을 한번 하게 된다.근데 이게 꽤 성능 차이가 난다고 하는데 아직 나는 겪어 본적이없다.. 어떤 사람이 2초 제한인 문제에서모듈러를 그냥 썼을 땐 TLE 가 났는데 저렇게 while 문..
전까지는 unordered_map 를 선언하고 이 안에 없으면 새로 추가하고 있으면 지나가는 식으로 했는데 코드 줄도 길어지고뭔가 지저분해졌지만 어쩔수 없이 썼었는데 이럴 필요가 없었다.. 보다 깔끔한 방법 두가지가 있다. 첫번째는 unique 라는 함수를 사용하는 것이다.정렬되어있는 벡터의 시작과 끝 iterator 를 인자로 주면 모든 수들을 한번씩만 써서 정렬한 sequence 를 맨앞에 오도록순서를 재배치 하고 그 끝 iterator 를 반환 한다고 한다. 그래서 이렇게한다.12345678910111213#include using namespace std; int main() { vector v({1,1,1,1,2,2,2,3,3,4,4,5,6,7,7,7,7,8,8,9,9,9}); sort(v.be..
https://oj.uz/problem/view/KRIII5P_3 \(1\leq{N}\leq{10^5},\,0\leq{s_{i},\,e_{i}}\leq{10^9}\)N개의 구간 \([s_{i},\,e_{i}]\) 가 입력으로 주어질 때(\(s_i\gt{e_i}\) 면 공집합)구간들의 교집합이란 \([max(s_1,\,s_2,\,\cdots,\,s_k),\,min(e_1,\,e_2,\,\cdots,\,e_k)]\)구간의 길이는 \(max(0,\,e_{i}-s_{i})\) 으로 정의 될 때선택된 구간들의 교집합의 길이가 1이상이도록 구간들을 선택할 때그 선택하는 방법의 수와 그 각각의 방법에서 교집합의 길이들의 합을 구하는 문제이다. 우선 방법의 수는 라인 스위핑으로도 풀 수 있고, 좌표압축+펜윅트리로도 풀..
https://oj.uz/problem/view/KRIII5P_2 \(0\le{N}\le{10^6},\,1\le{P}\le{10^3}\)N차 다항식 \(f(x) = a_{N}x^{N}+\cdots+a_{1}x+a_{0}\) 과 소수가 주어진다.이 때 \(f(0)\,mod\,P,\,f(1)\,mod\,P,\,\cdots,\,f(P-1)\,mod\,P\) 를 각각 구하는 것이다. 우선 가장 naive 하게 생각을 해보면f(x) 를 구하는데에 걸리는 시간을 생각해 보면 빠른 N제곱을 하는데에 O(lgN) 이 걸리기 때문에각 항을 계산하는데에는 O(lgN) 이걸리는데 항의 수가 N개 이기 때문에 O(NlgN) 이 걸린다는것을 알 수가 있다.그런데 P가지의 x 에 대해 계산을 하기 때문에 O(NPlgN) 의 시간..
http://codeforces.com/contest/803/problem/E N,K
http://codeforces.com/contest/803/problem/D 너무 간단한 파라메트릭서치문제이다. 보자마자 파라메트릭서치임을 알았는데 구현이 막혀서 1시간동안 풀이못했기에반성하는 마음으로 기록용으로 글을 올린다..(정확히는 파라메트릭서치가 아니라 바이너리 서치라는데 나는 파라메트릭서치가 편하다..) 공백, 하이픈(-), 알파벳 대소문자로 이루어진 문자열 한줄과 만들 수 있는 최대 줄 수 K를 입력받는다.공백과 하이픈에서 줄을 바꿀 수가 있을 때 K줄을 넘지 않도록 하는 최대 가로폭(width) 를 구하는 문제이다.가로폭은 각 줄의 길이중 최대인 길이를 말한다. 그럼 그냥 단순히 가로폭의 상한을 정해놓고 그 가로폭을 최대로 갖도록 최대한 한줄에 꾸겨넣을 때 줄의 수를K개 이하로 만들 수 있..
큰 수 N의 모든 약수를 구하는 방법.큰 수라는 것은 int 의 범위를 넘으면서 long long 의 범위는 넘지않는 정도의 크기를 가진 수라고 생각하면 된다.약수를 구하는 가장 쉬운 방법은 1부터 N 까지 모두 돌며 N 을 나눈 나머지가 0인 것을 모두 찾으면 된다.하지만 N이 매우 크기 때문에 O(N) 으로는 구할 수가 없다. 그렇다면 어떻게 할까약수들의 특성중의 하나는 서로 짝을 이룬다는 것이다. 다시말해서N의 약수 i 가 있으면 N/i 도 약수라는 것이다. 그렇기 때문에 i가 N^0.5 를 넘어가면, 만약 약수가 존재하더라도 어차피 앞에서 봐준 것이기 때문에 또 봐줄 필요가 없다. 즉, N^0.5 까지만 반복하면서 N 을 나눈 나머지가 0인 수 i를 찾고i 를 찾았다면 N/i 도 같이 찾아주면 된..
http://codeforces.com/contest/803/problem/C N,K = K*(K+1)/2 냐 라는 말이 같고먼저 GCD를 정해주고 이 GCD로 strictly increasing 하는 K개로 분리가 가능한지즉, 고정된 GCD로 K개의 수를 각각 나눠서 모두 더한 값이 K*(K+1) 보다 크거나 같은지를 판단하기만하면되기 때문에GCD를 최대로 하기위해 가능한 가장 큰 GCD부터 가장 작은 GCD까지 반복하며 가장 큰 GCD를 찾은 뒤N을 그 GCD로 나눠서 strictly increasing 한 K개의 수를 만들고(1,2,3,... 처럼 1씩 증가시키다가 마지막 K번째 수에 다 때려박으면됨)K개의 수에 모두 GCD를 곱해주면 답이 될 것이다.만약 N/GCD >= K*(K+1)/2 가 되는..
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3148 K
BOJ 9359번 : 서로소 1