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

이렇게 쉬운 걸 왜 틀렸는지 모르겠는데 틀려버렸다. 더 열심히 해야겠다. 끝나고 답안지 스캔하자마자 실수한게 보였다. 아침에 하는 수업이라 그런지 머리가 안돌아갔나보다... Q. prove that ad-bc=1,gcd(m,n)=1----> gcd(am+bn,cm+dn)=gcd(m,n) gcd(a,c)=1임을 쉽게 알 수있다. a-kc=1이 되는 k가 존재한다. gcd(am+bn,cm+dn)=gcd(m,(dk-b)n)이다. gcd(m,n)=1이므로 증명 끝. 실수한것. 마지막에 gcd(m,n)=1이용해서 증명했어야 하는데 a-kc=1d 이면서, dk-b=1이 되는 k가 존재한다고 썼다.

가장 큰일은 몇가지가 있기도 하고 없기도 하다... 역시나 ps로 인생을 낭비해버린 방학이었다. ps인생에 어느정도 큰 방점을 하나 찍었는데, 코포 퍼플을 달았다. 하지만 참여하는 모든 현실적인 대회마다 망하면서 남는게 없는 그런 방학이기도 하다. 이후부터는 우울한 후기가 될수도 있는데... 보기 싫으신 분들은 뒤로 가기 눌러주세요.. SCPC 2번문제에서 크게 말려서, 하다가 현타와서 그냥 도망갔다. 틀리면 안되는 문제였고, 심지어 풀이도 올바르게 짰었다. 아마 코딩미스땜에 틀렸는데, 나는 풀이자체가 틀린줄 알고 풀이를 바꾸는 짓을 해버렸고, 2번 solve수 보다가 그냥 나갔다. 올해 수상가능성이 낮다고는 생각했지만 제일 큰 대회중 하나 인만큼 정말 힘들었다. 내년에는 잘하고 싶다. Google Co..

현재 시각 기준 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.htm 6.구조체를 만들어서 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