블로그 옮겼습니다

https://www.acmicpc.net/problem/1044 \(2\leq{N}\leq{36}\) (N은 짝수) N을 입력받고, 10^15 이하인 자연수를 N개씩 두줄 입력받는다. N명의 사람은 1번팀 또는 2번팀에 들어간다. 각각의 사람이 어떤 팀에 들어갈 때 증가하는 팀의 전력이 주어진다.1번팀과 2번팀가 같은 수의 팀원을 가지며 두 팀의 전력차가 최소가 되도록 팀을 배정할 때 각각의 사람이 어떤팀에들어가게 되는지를 구하는 문제다.(만약 두 팀의 전력차가 같은 답이 여러개 있을 경우 사람들의 팀을 순서대로 나열한sequence 가 사전순으로 앞서는 것을 출력. 예를 들어 2 1 1 2 와 2 1 2 1 이 있으면 2 1 1 2 를 출력) 일단 naive 하게 생각해 보면 N이 최대 36이기 때문..

\(2\leq{N}\leq{50}\)\(0\leq{A[i]}\leq{N-1}\)N개의 원소로 이루어진 벡터 A가 주어진다. 벡터의 값들은 0과 N-1 사이값이며 중복되지않는다.\(0\leq{K}\leq{N-2}\)인 N-1가지의 K에 대해 각각 한번씩 swap(A[K], A[K+1]) 을 해야만 한다.그렇다면 이 swap을 하는 순서에 따라서 주어진 벡터의 결과값이 달라질 것이다.그렇다면 주어진 벡터가 0,1, ..., N-2, N-1 과 같은 형태로 오름차순 정렬되도록 하는 swap 순서는 총 몇가지가 있는지를구하는 문제이다. 이 문제는 DP로 풀 수가 있다. \(dp[i][j]\,:\,[i,\,j]\) 의 구간을 오름 차순 정렬하는 방법의 수오름 차순 정렬이라는 것은 [i, j] 구간에 어떤 수들이 ..

1234memset(d,0,sizeof(d)); for (i=0;i

이건dy[4] = {0, -1, 1, 0};dx[4] = {-1, 0, 0, 1};을 하여 상하좌우 dfs 돌릴 때 많은 쓰는것을 따로 dy,dx 를 선언하지않고 한줄에 처리하는것이다.. 그리고cout

https://oj.uz/problem/view/KRIII5_UV \(1\leq{N}\leq{10^4}\)\(-10^{14}\leq{A[i]}\leq{10^{14}}\)N이 주어지고 N개의 정수로 이루어진 배열 A가 주어진다.이 배열을 여러개로 나누는데 나눈 각각의 덩어리에 속한 원소의 합이 같도록 나눠야한다.이렇게 나누는 모든 방법의 가짓수를 구하는 문제이다. 물론 1e7 로 나눈 나머지를 구한다. 이 문제는 dp 문제이다. 각 덩어리의 원소의 합을 몇으로 같게 할지를 먼저 정해주고K로 정했다면 합이 K 가 되도록 나누는 방법의 수를 dp로 구한다.dp[i] : i번째 원소부터 합이 원소들의 합이 K인 덩어리들로 나누는 방법의 수그리고 모든 가능한 K에 대해 메모이제이션한 것을 초기화해주고 다시 부분문..

이건 확실한건아니고 들은 사실인데 모듈러를 많이하면 생각보다 속도 저하가 있다고한다. 그래서 코포에서 고수들도모듈러 연산을 줄이는 테크닉을 많이 쓴다고 들었는데 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