블로그 옮겼습니다

N개의 컴포넌트들이있고 판떼기가 하나있다. 판떼기는 앞면과 뒷면이있다. 각 컴포넌트를 판떼기에 모두 붙이고싶은데 하나의 컴포넌트를 앞면에 붙이는 비용과 뒷면의 붙이는 비용은 다르고각 컴포넌트마다도 비용이 또 다르다.그리고 특정 컴포넌트들은 무조건 앞면 혹은 뒷면에 부착해야 된다는 조건이 주어진다.-1 이면 뒷면에, 1이면 앞면에 붙여야하며 0이면 어떤면에 붙여도 상관없다는 것이다.그리고 M개의 제한이 주어지는데 각 제한의 내용은 특정 두 컴포넌트를 다른 면에 붙였을 때에는추가적인 비용이 발생한다는 것이다. 각 제한마다 두 컴포넌트와 추가 비용은 다르다.이 때 N개의 컴포넌트를 모두 판떼기에 붙이는 최소 비용을 구하여라. 이 문제는 min-cut 문제이다. source -> 컴포넌트 -> sink 와 같은..

http://codeforces.com/contest/821/problem/D \(n,m,k\le{10^4}\)세로 n, 가로 m 인 n * m 크기의 격자판의 (1,1) 에서 (n,m) 까지 이동하고싶다.격자판의 k개의 칸에는 불이 켜져있다. (1,1)은 무조건 켜져있다. 이동할 때에는 무조건 불이 켜져있는 칸만 밟을 수가 있다.하지만 코인 1개를 사용하면 한 행 전체, 혹은 한 열 전체의 불을 켤 수가 있다.한번에 하나의 열 또는 행만 켤 수가 있으며 만약 불을 켜는 행이나 열을 바꾸고 싶다면원래 부터 불이 켜져있던 칸으로 이동을 해야 한다. 물론 바꾸면 이전에 켠 행(열)은 원래 켜져있던 칸을 빼고는 다 꺼지고 새로운 행(열)이 켜지며 또 코인 1개가 든다.이 때 (1,1) 부터 (n,m) 까지가는..

https://csacademy.com/contest/archive/task/second-minimum/ 반씩 나눠가며 각각의 l, r 에 대해 작은 값을 가지고 있다면 한번 분할정복 돌리면 가장작은 값은 바로 나오며그다음에 토너먼트의 승패표가 있을 때 2등의 후보는 lgN개로 정해져있는 성질이 있기 때문에 다시 순회하면서lgN개에 대해서만 반복문 한번 돌리면서 가장 작은놈을 구해주면 된다.2등의 후보는 결승에서 1등한테 진놈, 준결승에서 1등한테 진놈, 준준결승에서 1등한테 진놈, ..... ,1라운드에서 1등한테진놈이 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include using namespa..

https://algospot.com/judge/problem/read/COUNTPALIN \( 1\leq{N}\leq{10^6} \)길이가 N인 문자열 S가 입력으로 주어질 때 팰린드롬인 모든 부분 문자열의 개수를 구하는 문제이다.이 문제를 푸는 방법은 우선 각 중심마다 최대 팰린드롬의 길이를 구한뒤 그 길이/2 만큼을 모두 더해주는 것이다.왜냐하면 어떤 중심에서 최대 길이의 팰린드롬이 abccba 라면 같은 중심을 가지는 팰린드롬들은 반지름을 1씩 줄여나가면모두 팰린드롬이기 때문에다. 이것은 자명하다. 즉, abccba, bccb, cc 이게 다 팰린드롬이 되기 때문에 최대팰린드롬길이/2의 식이 나오는 것이다. 그리고 중심이 다르면 다른 팰린드롬이라는 것이 자명하기 때문에 모든 각각의 중심에 대해최대..

N 명의 사람이 각각 선물을 하나씩 준비해왔을 때 모두가 자신이 준비한 선물 이외의 선물을 갖도록 나눌 때그 경우의수를 구하는 문제 1 2 3 4 5 다섯명의 사람이 있다고 가정하자.맨 처음에 1번사람은 자신의 선물이 아닌 나머지 사람들의 선물, 즉 n-1 개의 선물을 가질 수 가 있다.그럼 그중에 하나의 경우인 1번사람이 2번사람의 선물을 가질 때를 생각해보자.그럼 2번사람이 받는 선물은 두가지 경우로 나뉜다. 첫번째, 1번사람의 선물을 갖는 경우. 그럼 1번 사람과 2번사람이 선물을 둘이 교환한 것과 같게 되므로D[i] : i명의 사람이 자신의 선물을 안갖도록 선물을 교환하는 경우의수일때, 교환한 두명을 제외한 나머지 n-2명에게 같은 행위를 반복하므로 D[n-2] 가 된다. 두번째, 1번 사람이 아..

1 T; for(int t = 1; t > P; ll S = 1e12; ll GCD = gcd(P*S, S); ll C = S/GCD; S = P * C; S -= C; ans[4] = S/4; if(S%4) ans[S%4]++; ans[0] = C - ans[1] - ans[2] - ans[3] - ans[4]; cout

예를 들어 소수 0.375 를 정수로 만들어 주기 위하여 곱해야 하는 최소 정수는 몇일까?답은 40이 나와야 한다.10의 거듭제곱꼴인 매우 큰 수 S가 있다고 하자. 그리고 주어진 소수를 p라고 해보자.그러면 p*S 는 정수가 될 것이 분명하다. (물론 가장 낮은 소수점 자릿수보다 10의 지수가 크거나 같아야만 한다)그렇다면 gcd(pS, S) 를 해보자. 만약 p가 정수였다면 gcd(pS, S)는 S임이 자명하다. 하지만 p 가 소수이기때문에p를 정수로 만들어 주기 위한 S의 최소 약수만큼이 빠질것이다. 그렇다면 p를 정수로 만들어 주기 위한 S의 최소 약수는 S/gcd(pS, S) 가 될 것이다. 그런데 잘 생각해 보면어떤 소수를 분수의 합꼴로 나타내보면, 즉 3*(1/10^(-1)) + 7*(1/1..

개인적으로 가장 알아야한다고 생각하는 네가지를 쓰겠다. 1번째\(\binom n k = \binom {n-1}{k} + \binom {n-1}{k-1}\) 예를 들어 생각해보면 쉬운데 어떤 반에서 n명의 학생중 k명의 대표를 뽑으려고하는데 이 때의 경우의 수는특정 학생 x 에 대해 두가지의 케이스로 나누어 생각해 볼 수가있다.학생 x를 뽑는 경우와 뽑지 않는 경우 이렇게 두 가지의 케이스이다.만약 학생 x를 뽑는다면 나머지 n-1 명의 학생들 중에 k-1명의 대표를 더 뽑아야 하므로 \(\binom {n-1}{k-1}\) 가지의경우의 수가 있으며, 학생 x를 뽑지 않는다면 나머지 n-1 명의 학생들 중에 k명의 대표를 뽑아야 하므로\(\binom {n-1}{k}\) 가지의 경우의 수가 있다. 그래서 두 ..

문제 링크 \(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의 곱으로 이루어 지기..

처음엔1234567ans = 0; map mp; if(mp[어떤답] == 0) mp[어떤 답] = 1, ans++; Colored by Color Scriptercs이렇게 했었는데 굳이 이렇게 할 필요없이 그냥 set에 넣고나서 마지막에 set.size() 를 하면 쉽게알수있다..