acmi 님의 블로그

해당 글에서는 USACO 2024 December Contest Silver 1, 2번 문제의 풀이를 간단히 설명하고자 한다. 1. Cake Game https://usaco.org/index.php?page=viewproblem2&cpid=1446 Elsie는 왼쪽, 오른쪽 끝에서부터 시작해서 연속하여 케이크를 원하는 대로 총합  N/2개를 먹을 수 있으므로 Elsie가 먹게 되는 케이크의 양은 처음 상태에서 Elsie만 N/2번 가져갈 때의 최댓값 이상이다.  Bessie는 다음과 같은 방법을 통해 Elsie가 최댓값보다 더 많이 가져가지 못하게 할 수 있다: 자신의 차례에서 놓여있는 짝수개의 케이크 중 가운데에 있는 두 케이크를 합친다. 이렇게 하면 Elsie의 차례에서 합쳐진 케이크는 홀수개의 케..

https://www.acmicpc.net/problem/13428알고리즘: fft 풀이(대문자와 소문자가 의미하는 바가 다르다):배열 a[i]와 b[i]를 각각 배열 A와 배열 B에서 i(0두 배열 a, b에 대해 합성곱에서 두 수의 곱셈을 두 수 중 크지 않은 것(c++에서 min함수)으로 바꾼 식을 계산하면 풀 수 있다(단, 배열 a, b의 크기 n은 200000이상으로 하고 100000부터는 a[i]와 b[i]는 0으로 하자). $ c[j]=\sum_{i=0}^{n-1}min(a[i],b[j-i])$ 나이브하게 계산하면 시간 복잡도는 $O(n^{2})$가 되고 시간초과가 난다. i와 j가 0 or 1일때 min(i,j)=i*j임을 이용하자.  f(x)를 x가 양수면 1, 그렇지 않으면 0으로 정의..

유클리드 호제법으로 gcd를 구하는 방법은 다음과 같다:두 자연수 a>b에 대하여 gcd(a,b)=gcd(b,a%b)임을 이용해 두 수 중 큰 것을 작은 것으로 나눠 그 나머지로 대체한다. 이 때 두 수 중 하나가 0이 되면 남은수가 gcd이다. 코드로 구현하면 다음과 같다:int gcd(int a,int b){//a>0, b>0if(b==0)return a;return gcd(b,a%b);}b>a%b이므로 다시 호출되었을 때는 a>b를 만족한다. 그러므로 b가 0인지만 확인하면 된다.a>b를 만족하지 않고 a>0, b>0이기만 해도 된다. 왜냐하면 a이면 gcd(b,a)가 다시 호출되기 때문이다. c언어에서는 a가 음수일 떄 a%b를 음수 또는 0으로 계산하므로 a>0, b>0이도록 해야한다. 양수로 ..