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

1.$sin(pi*f(0))=0$이어야 한다. 2.$g(x)=sin(pi*f(x))$로 두면 $g'(0)=0$ 이다.이를 풀면 $cos(pi*f(0))=0$ 이거나 $f'(0)=0$ 인데, sin 과 cos 은 동시에 0일 수 없으므로 $f'(0)=0$ 아주 중요한 조건을 얻었으므로 $f(x)=9*x^2(x-3a) + c$로 둘 수 있다. 여기서 문제의 조금 아래를 보면, $g(x)$가 실수 전체의 연속이므로, $g(0)=g(1)$ 따라서 $c=9*(1-3a)+c$. 따라서 $a=1/3$ 극댓값은 $c$, 극솟값은 $c-4/3$ (계산해보면 된다.) 곱해서 5가 된다는 조건을 해석하면 $c=-3/5$ or $ c=3 $ 그런데 1번 조건에 의해 c=3. 따라서 $9x^2(x-1)+3$ 계산 쉽게 하기. ..

오답률 높은거부터 쭉 풀어보고 있는데 조금 쉬운걸 보니 문제 자체가 준킬러가 여러개인 유형으로 바뀌는 중인가 보다. 수험생이 아니라 확실히는 모르겠다 ㅎㅎ. g(x)를 살펴볼때 f(x-3) 오른쪽을 잘 살펴보는게 중요하다. h(x)=|f(x)|로 보면 오른쪽 식은 -2*h'(x)임을 쉽게 보일수있다. 그렇다면, g(x)의 서로 다른 실근은, f(x-3)=0인점,h'(x)가 0인점이다. 어떤 함수에 절댓값 함수를 씌우면, y=0이라는 직선을 긋고 위로 뒤집는다. 삼차함수에는 여러가지 꼴이 있는데, g(x)의 실근의 개수가 4개이려면, y=0에 접하는 x가 있다는 것을 알 수 있다. 따라서 f(x)=(x-a)^2(x-b) 꼴이어야 한다. 이때, f(x-3)=0의 근은 a+3,b+3이고, h'(x)=0의 근은..

이렇게 쉬운 걸 왜 틀렸는지 모르겠는데 틀려버렸다. 더 열심히 해야겠다. 끝나고 답안지 스캔하자마자 실수한게 보였다. 아침에 하는 수업이라 그런지 머리가 안돌아갔나보다... 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...