코드포스19 Educational round #75 D - Salary Changing ( 이분탐색 ) https://codeforces.com/contest/1251/problem/D 보자마자 이분탐색이나 dp겠구나 싶어서 이분탐색으로 접근했다. 하지만 시간이 부족해서 10분정도 오버해서 풀었다. 설명) 사람의 수 n과 가지고 있는 돈 s가 주어지고 n명의 사람에 대해 받을 수 있는 돈의 범위 [l,r]이 주어진다. 이 때 사람들에게 나누어주는 돈의 중간값의 최대를 구하는 문제이다. l을 기준으로 사람들을 오름차순 정렬한다면 l, l, .... l, m, max(m,l), max(m, l) ... max(m,l) 인 경우가 최적이다. m값을 기준으로 오른쪽에 위치할 수 있는 사람은 r의 값이 m이상이어야 한다. 중간값 우측의 사람 수가 n/2미만이라면 그 값을 중간값으로 사용할 수 없다. 이 부분이 생각.. 2019. 11. 9. Educational round #73 D - Make the fence great again (dp) https://codeforces.com/contest/1221/problem/D 한 부분 당 최대 2만큼 늘릴 수 있다는 것을 가정하고 dp모양은 만들었지만 예외가 있을 거라 생각하고 삽질함.. i==0일 떈 그냥 0~2번 다 확인해주고 i>0 일 떈 i-1의 상태와만 비교해주고 인자로 본인이 얼마나 늘렸는지만 같이 넘겨주면 된다. #include #include using namespace std; typedef long long ll; const ll MAX = 3e5 + 1; const ll INF = 1e18 + 1; int n; ll dp[MAX][3]; int h[MAX], c[MAX]; ll f(int k, int x) { if (k == n) return 0; ll& ret = dp[k].. 2019. 11. 7. codeforces #581 div2 C - Anna, Svyatoslav and Maps ( 플로이드 ) https://codeforces.com/contest/1204/problem/C 루프가 없는 단방향 그래프에 대해, 임의의 경로를 입력으로 주고, 그 입력의 처음과 끝은 그대로이지만 경로는 똑같을 수 밖에 없는 정점의 배열을 출력하는 문제. (물론 그 배열의 크기는 최소가 되도록.) 위와 같은 그래프와 입력이 1 2 3 4 1 2 3 4 일떄 출력은 1 2 4 2 4 이다. 1 3 4 2 4가 안되는 이유는 3번 정점을 방문하면 입력한 경로에서 벗어나기 때문이다. 풀이) 1. 첫번째 정점과 마지막 정점은 항상 출력해야 한다. 그리고 int arr[]에 입력 경로가 담겨있고, vector ans에 출력할 정답을 담는다고 하자. (pair엔 정점번호, 입력배열에서의 인덱스) 여기서 인덱스를 저장하는 것은 .. 2019. 11. 4. 치킨 맥너겟 이론 (chicken mcnugget theorem) https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem 1) 소수 m, n와 임의의 정수 a,b로 나타낼 수 없는 am+bn(소수m,n의 linear combination)의 최대값은 mn-m-n이며 이를 초과하는 수는 모두 am+bn으로 나타낼 수 있다. 또한 am+bn으로 나타낼 수 없는 값의 개수는 다음과 같다 2) 소수가 아닌 일반 양의 정수 m, n에 대해서도 일반화 한다면, 우선 m,n의 linear combination인 am+bn을 다음과 같이 변환한다. 위 두개는 서로소이므로 이들에 대해서 치킨맥너겟 정리를 적용하면 아래와 같이 정리된다. gcd(m,n)을 마저 곱해주면 따라서 lcm(m,n)-m-n을 초과하는 gc.. 2019. 11. 3. 이전 1 2 3 4 5 다음
