블로그 옮겼습니다

문제 링크 \(1\leq{a,b,c}\leq{10^9}\) 일 때, A * B = C 를 만족하면서 |A-a| + |B-b| + |C-c| 가 최소가 되게 하는 자연수 A,B,C 에 대하여|A-a| + |B-b| + |C-c| 를 구하는 문제이다. 처음에 삼분탐색 등으로 구하려 했는데 풀리지 않았다. 애초에 삼분탐색만으로는 풀 수 없는 문제같다.우선 가장 중요한 것 중 한가지는 A가 정해지면 |A-a| + |B-b| + |C-c| 가 최소값이 되기 위한 B와 C는자동으로 결정 된다는 것이다. 그 이유는우선 우리는 A가 이미 정해졌기 때문에 |A-a| + |B-b| + |C-c|를 최소로 만들기 위해서는 최대한B를 b와 같게 만들고 C를 c와 같게 만들어야 한다. 그런데 C는 A와 B의 곱으로 이루어 지기..

https://www.acmicpc.net/problem/10166 \(1\leq{D1}\leq{D2}\leq{2000}\)이 문제는 가운데에 콘서트장이 있고 그 주위로 동심원들이 있을 때, D1, D2가 입력으로 주어지면각 원내에서 거리가 일정하게 D1, D1+1, D1+2, D1+2, ... , D2 개를 각각 놓고 싶을 때 겹치는 위치가 있다면앞이 잘 보이지 않으므로 맨 앞에 한 좌석만 남기고 뒤에 좌석은 배치하지 않는 것이다.이 때 총 필요한 좌석의 수를 구하는 문제이다. 사실 동심원이 여러개 있는 것이 아니라 원이 하나 있고 그 안에 거리가 일정하도록 D1개의 점을 찍고그 다음에 같은 원에 거리가 일정하도록 D1+1개의 점을 찍고 를 계속 반복했을 때 찍히는 점의 수를 구하는 것과 같다. 우선 ..

\(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

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) 의 시간..

큰 수 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 가 되는..

BOJ 9359번 : 서로소 1

http://codeforces.com/problemset/problem/577/B n and m (1 ≤ n ≤ 106, 2 ≤ m ≤ 103) sequence의 길이 n과 m 이 주어지는데 원소의 합이 m 으로 나누어 떨어지는 subsequence 가 있는지 없는지 판별 하는 문제이다. 처음엔 일종의 dp 로dp[i][j] = subArray[~i] 의 subsequence 중 원소들의 합을 m으로 나눈나머지가 j 인 subsequence 가 있는지로 매 배열의 원소마다 선택을 하는 경우와 선택을 하지 않는경우로 나누어서 배열을 update 해주는 식으로 했는데생각해보니 그렇게 되면 시간 복잡도가 O(n*m) 이어서 TLE 가 난다. 좀 생각을 해봤는데 잘 모르겠어서 Editorial 을 봤는데 두가..