gubshig

https://www.acmicpc.net/problem/24477 재밌는 JOI 문제이다. 서브태스크마다 풀이를 생각해본 문제는 오랜만인데, 마침 메모장에 적어놓은게 몇가지 있어서 블로그에 올려볼까 한다. subtask 1) $A(i) \to [A(i) + 1, B(i)]$ $A(i) + 1 \to [A(i) + 2, B(i)]$ $A(i) + 2 \to [A(i) + 3, B(i)]$ $\min(A(i) + k - 1, B(i) - 1) \to [\,, B(i)]$ ... or $A(i) \to [B(i), A(i) - 1]$ $A(i) - 1 \to [B(i), A(i) - 2]$ $A(i) - 2 \to [B(i), A(i) - 3]$ $\max(A(i) - k + 1, B(i) + 1) \to ..

https://www.acmicpc.net/problem/27877 27877번: 제곱수 덱 2 $x$의 최솟값을 $998\,244\,353$로 나눈 나머지를 출력한다. 만약 $N$장의 카드를 하나의 덱으로 합칠 수 없다면 -1을 출력한다. www.acmicpc.net 문제가 상당히 간단하다. 관점을 조금 바꿔보자. 각 카드를 정점으로, 덱을 컴포넌트로 보면, 이 문제는 MST 문제로 환원될 수 있다. 가중치 간선의 곱에 대한 MST인데, 결과에 log를 씌운다 하면, 결국 곱셈이 덧셈으로 바뀌기에, 일반적인 MST 문제와 같다. 크루스칼 알고리즘을 생각해보자. 가중치가 적은 간선부터 선택하며 만약 그 가중치를 선택할 때 사이클이 생긴다면 선택하지 않는 식으로 작동하는 알고리즘이다. 예제어서 주어진 14..

https://www.acmicpc.net/problem/26973 26973번: Circular BarnFor the first test case, Farmer John can remove $1$, $2$, or $3$ cows from the first room. Whichever number he removes, Nhoj can remove the remaining cow(s), forcing FJ to lose when they circle back to the first room. For the second test case, FJ can removwww.acmicpc.net  일단 N = 1인 경우를 생각해보자. 편의상 Farmer John을 FJ라 하고, Farmer Nhoj를 FN이라 부르..

https://www.acmicpc.net/problem/16136 16136번: 준하의 정수론 과제 (Divmaster) 준하는 3학년 2학기 때 들으려고 했던 정수론을 수강신청을 잘못하는 바람에 2학년 1학기 때 신청하고 말았다! 사악한 정수론 선생님은 자연수의 약수의 개수를 구하는 문제를 던지고, 이 문제 www.acmicpc.net 일반적인 세그먼트 트리나 레이지 세그먼트 트리로는 해결할 수 없음을 알 수 있다. 관찰을 하나 하면 문제가 쉽게 풀린다. 약수의 개수 함수를 d(n)이라고 하자. d(n)을 반복하다보면 그 수가 1이 아닌 이상 2에 수렴할 것인데, 그 속도가 상당히 빠름을 알 수 있다. 어떤 수의 약수의 개수의 상한은 2 * sqrt(n) 정도 되기 때문이다. 그렇다면 어떤 수가 2에..

오늘 수업 때 배운 테크닉인데, 상당히 간단하고 또 범용적이어서 한번 정리해볼까 한다. 원하는 원소들 중 최소, 최대를 관리해주고 싶으면, 우선순위 큐라는 자료구조를 사용할 수 있다. 하지만 원소를 삭제하고 싶다면 어떻게 해야할까? 가장 쉽게 생각할 수 있는 방법은 세그먼트 트리를 사용하는 것이다. 하지만 상수가 크고, 메모리도 더 잡아먹기에 추천하지 않는다. 현재 있는 원소와 삭제된 원소를 담아주는 우선순위 큐 2개를 관리해줄 것이다. 삽입 연산은 그냥 해주면 되고, 삭제 연산은 삭제된 원소를 담아주는 큐에 push해주면 된다. top을 볼 때는 삭제된 원소를 관리해주는 큐와 그냥 큐의 top을 비교해주며, 만약 같다면 둘다 pop해주고, 다르면 그냥 큐의 top이 우리가 원하는 top 값이 된다. 큐..

어제 다른 분들이 쓴 USACO 후기를 조금 찾아봤는데, USACO 2020 December Contest 후기글을 찾았습니다. 일단 문제를 풀고 글을 읽고 싶었어서, 틈틈히 풀었습니다. 문제가 상당히 재밌었던 것 같습니다. 실제 풀이에 쓴 시간은1번 10분2번 30분3번 1시간정도 된 것 같습니다. https://www.acmicpc.net/problem/20647 20647번: CowntagionOne possible sequence of events corresponding to this example is the following: the number of sick cows in farm 1 doubles and then doubles again, so that after two days, the..

유사코가 끝난지 꽤 되었는데, 귀찮아서 풀이를 올리지 않다 이제야 올린다. 당시 대회에서 2, 3번을 1시간 30분정도에 걸쳐 풀고, 1번 문제를 계속 봤는데, 결국 섭테를 하나도 못긁었다. 이상한 관찰을 자꾸 하고 증명도 없이 살면서 풀어본적도 없는 기하적 해석을 했는데, 결국 그냥 뻘짓이었다. 다음부터는 문제가 어려워보이면 섭테 긁을 생각부터 해야겠다. https://www.acmicpc.net/problem/27847 27847번: Cow-libi Somebody has been grazing in Farmer John's $(1 \le G \le 10^5)$ private gardens! Using his expert forensic knowledge, FJ has been able to dete..

https://www.acmicpc.net/problem/15587 15587번: Cow at Large (Gold) Cornered at last, Bessie has gone to ground in a remote farm. The farm consists of $N$ barns ($2 \leq N \leq 10^5$) and $N-1$ bidirectional tunnels between barns, so that there is a unique path between every pair of barns. Every barn which has only one tun www.acmicpc.net 요즘 유사코 실~골 div를 돌고 있는데, 여기는 문제 난이도가 적당하고 굉장히 맛있는 것 같다. 다양한 ..

선린에 입학하고 1년동안 알고리즘 공부를 어떻게 했는지 적어볼까 한다. 제대로 한 기간은 얼마 되지 않지만, 요즘 들어 점점 실력이 늘고 있는게 보여 뿌듯하다. 2021 12월 - 백준을 처음 알게 됨 그전에도 알고리즘이 뭔지는 알고 있었지만, 공부해본적은 한번도 없었다. 앱 개발을 포트폴리오로 제출해서, 선린 특별전형에 합격했고, 그 이후 신입생 단톡방에서 백준을 처음 알게 되었다. 처음 봤을 때 재밌어보여서 몇번 끄적이다 귀찮아서 그만두었던 기억이 난다. 이분탐색을 이때 배웠다. 2022 7월 - 선린 천하제일 코딩 대회에 나가다 뭔가 재밌어보여서 친구들과 함께 참가했다. 나 - 브론즈 5, 친구1 - 언랭, 친구2 - 실버5 조합으로 나간 대회였다. 그 당시 나는 파이썬으로 입출력을 받을 줄도 몰라..

어제는 애니메이트를 다녀오느라 문제를 거의 못풀었다.. 오늘은 4문제를 풀었다. 다 꽤 재밌는 문제였다고 생각한다. https://www.acmicpc.net/problem/10166 10166번: 관중석 KOI 공연장의 관중석에는 가운데에 있는 무대를 중심으로 반지름이 자연수인 동심원(중심이 같은 여러 원들) 위에 다음과 같이 좌석들이 배치되어 있다. 반지름이 1인 원 위에는 좌석이 1개, 반지 www.acmicpc.net 이 문제는 여러가지 풀이법이 존재한다. 유클리드 호제법을 사용한 O(d2 ^2 log d2) 정도의 풀이가 정해인것 같다. 나는 dp로 O(d2 log d2)에 풀었다. 기본적인 관찰: 반지름이 r인 동심원에 대하여, 반지름이 r의 배수인 동심원들과 정확히 r개의 좌석이 겹친다. d..