노력하는 공대생의 공부일지

현재 시각 기준 15명에게밖에 풀려있지 않은 문제다. 매우 좋은 dp문제라는 생각이 들어서 풀이를 올린다. 1.배송비가 없다면 어떤 문제일까? mcmf의 기본형태이다. 2.배송비가 있을때 naive한 dp를 떠올려보자. 그렇게 되면 시간복잡도가 test case1개당 $O(NMS)$정도에 풀수 있고, 이는 너무 크다. (tc가 1개라면 적당히 최적화 할 여지가 존재한다.) 여기서 최적화를 잘하면 $O(NS)$정도에 줄일수도 있는데, 이렇게 해도, tc가 100개라 tle가 난다.(해보진 않음..ㅋㅋ!) 3.그리디한 전략 하나를 섞자. i번째 쇼핑몰에서 구매하기로 결정했으면, 그 쇼핑몰에서 항상 모든 물건을 구매하거나, 그 쇼핑몰이 마지막 쇼핑몰인 경우가 최적해이다. proof: 모든 물건을 구매하지 않은..

구글링해도 풀이가 없다. 코포 D번 같은 문제다.. 언제 한번 나와라! 우리는 뒤에서 부터 보는게 무조건 좋다. 즉, $(a,b)$ -> $(c,d)$ 보다는 $(c,d)$ -> $(a,b)$로 접근하자. 왜 그렇게 하냐면, $*2$라는 연산은 아무 제약이 없이 할 수 있지만, $/2$라는 연산은 짝수일때만 가능하기 때문이다. 그러면 이제 다음과 같은 특이한 사실이 성립한다. 현재 c와 d의 홀짝성이 다르다면, -1만 사용해야 한다. (나누기 2를 사용하려면 둘다 짝수 즉, 둘다 2로 나눈 나머지가 같아야 하고, 빼기 1 연산은 두 개의 홀짝성이 동시에 반전된다.) 둘다 홀수라면, 나눌수 없으므로 항상 -1 해줘 야한다. 짝수라면 2로 나눌수 있으면 나누는게 이득이다. 그 이유는 둘다 -1을 해버리면, ..

https://www.acmicpc.net/problem/22900 문제요약: 트리가 주어지고 간선에 가중치가 주어진다. 간선은 가중치가 존재할 때만 이용할 수 있다. 한번 움직일때마다 가중치를 원하는 만큼 뺀다. 움직일 수 없게 되는 사람이 지게 된다. 모든 시작위치에 대해서 선/후 공 중 누가 이기는지 구해라. 우선 가중치를 없애자. 어차피 모든 간선은 1번만 이용하는 걸로 생각해도 된다. (왜 그런지는 생각해보자.) 그럼 다음과 같은 tree dp형태로 바뀐다. 승리를 1, 패배를 0으로 칠한다면, 시작정점과 인접한 정점들 중에 0인 정점이 있다면 승리하고, 아니면 패배한다. 근데 모든 시작점에 대해 이걸 다 구하기는 어렵다. 그래프가 아니라 트리라는 걸 이용하자. 1번 정점을 루트로 잡고 dfs로..

1. x mod y =x - y (x/y)2. 곱의 최소를 로그값들의 합의 최소로 바꿀 수 있다. 3. 놀랍게도 어떤 수의 자리수를 모두 곱한 값은 그 수 보다 작다.  4. 단조 감소/증가가 동일한 함수 끼리의 min/max 함수는 단조증감을 바꾸지 못한다. 5.http://mathman.kr/math/pita.htm6.구조체를 만들어서 pq로 정렬할때 굉장히 큰 시간이 걸린다.  7.tree에서 모든 두 정점사이 단순경로 xor distance ---> 루트까지 xor이용해서 구하기. 8.부분구간은 구간합으로 생각해보기.(역으로 생각하기) 9.어떤 정수 a 가 있고 p와 서로소인 x를 생각하자. 그럼 a,a+x,a+2x,a+3x,.....a+(p-1)x 를 p로 나눈 나머지는 0~p-1을 전부 가진다..

팀연습에서 만난, 내가 업솔빙한 것 중에 재밌는 문제들을 모아보았다. 계속 업데이트 할 예정이다. 브라질 문제들은 코포에서 보면 영어로 볼 수 있다. 2020 brazil sub-regional https://www.acmicpc.net/problem/20283 https://www.acmicpc.net/problem/20284 https://www.acmicpc.net/problem/20280 https://www.acmicpc.net/problem/20289 진짜 2020브라질 서브리저널 갓-셋이다. 2019 brazil sub-regional https://www.acmicpc.net/problem/17539 https://www.acmicpc.net/problem/17535 https://www...

매일 매일 2200rating이하들 문제 못푼것중에 하나 골라서 풀고 있다. 2200짜리 문제였는데, 내가 풀이를 보지 않고 푼 것중에 가장 rating이 높은것 같다. 게다가, 정말 educational한 문제인거 같아서 마음에 들어 풀이를 쓰려고 한다. https://codeforces.com/contest/1537/problem/F Problem - F - Codeforces codeforces.com 문제 한줄요약 간선을 골라 양끝점의 가중치에 임의의 정수를 더할 수 있다. 모든 정점들의 가중치를 주어진 배열대로 만들 수 있는가? 사실 내가 최근에 푼 여러 그래프 문제풀이중에 중간에 부분 문제를 coloring으로 환원 시키는 여러가지 문제가 있었다. (이것도 애드혹 중에 하나 인가? 좀 유명한 ..

게임이론 주제는 코포나 ps에 있어서 굉장히 자주 나오는 주제이다. 애초에 수학적으로 재밌는 주제이기도 하고, ps에서는 dp라는 해결방식을 통해, 컴퓨터의 계산능력을 이용해서 무지성으로 뚫어버리는 풀이가 가능하기 때문에 자주 사용하는 것 같다. 우선 이 글에서 스프라그-그런디 정리는 배제하고 설명하겠다. (스프라그 그런디 정리는 궁금하면 꼭 찾아보길 바란다. 코포에 안나오기는 하는데, 백준 연습문제도 많고 icpc셋 돌다가 한 두번 마주친 것 같다.) game 문제를 풀 때 중요하게 생각해야 할 것은 4가지 정도가 있는 것 같다. 1.지는 상태를 회피 할 수 있는가? 2.항상 이기는 전략이 존재하는가? 3.전략은 모르지만 규칙성이 존재하는가? 4.무지성 dp로 해결이 가능한가? 1. 지는 상태를 회피 ..

slope trick 연습문제 이다. 기억이 휘발되기 전에 풀이를 써본다. https://www.acmicpc.net/problem/19693 개인적으로 이 문제는 풀이를 보지 않고 푸는 거를 추천한다. 풀면서 slope trick에 대한 이해가 깊어졌다.. 더보기 기본으로 배웠던 boj수열 문제와는 다르게 함수의 왼쪽 오른쪽 구간을 동시에 관리해야 한다. 우선 $dp(x,y)=min(dp(x-1,y))+|a(x)-x|$가 된다. 단 ($x-k

ㅋㅋㅋㅋㅋㅋ 수많은 try와 함께 결국 맞췄다. https://www.acmicpc.net/problem/2209 솔루션은 의외로(?) 쉽게 나온다. 근데, 내가 좀 바보짓을 해서 TLE가 계속 떴는데.... 두 중심지 H1,H2이 있다고 가정을 하면 1. H1끼리 연결된 곳에서 최대거리가 나오는 경우 2. H2끼리 연결된 곳에서 최대거리가 나오는 경우 3. 둘 사이를 가로지르며 최대거리가 나오는 경우 3가지 경우가 있는데, 두 노드를 중심으로 둘중에 노드를 골라서 연결한다고 가정을 하면, bruteforcing시 $O(2^N*N^2)$이된다. 조금 최적화를 해보면, H1에 A번째 노드를 연결을 해서 노드의 최장거리가 나올때의 경우로 생각을 하면, H1과의 거리가 A보다 긴녀석들을 전부 H2에 연결을 하..

https://www.acmicpc.net/problem/5484 문제설명은 힌트로 대체한다. 우리는 겹치지 않는 두개의 직사각형을 골라야 한다. 각각의 직사각형 내부에, 장미가 k개 있으면 된다! 요즘 ps에 대한 자신감이 하락하고 있었는데, 어떻게 갑자기 플레1을 내힘으로 풀었다! 어려운 문제 푸는게 확실히 구현력, 사고력에 도움이 되는듯. 정해는 모르겠는데 나는 $O(logN*N^2)$에 해결했다. 어떻게 풀까? prefixsum+binary_search+dp로 해결 가능하다. 우리가 1번 직사각형을 선택한다고 해보자. 그럼 전체 꽃밭에 있어서, 1,2,3,4,5로 나누어진다. (각각 겹치는 부분이 있다.) 1. 2차원 prefix_sum으로 우리가 원하는 범위에 꽃이 몇개있는지를 O(1)에 가져오..