gubshig

몇일동안 푼 문제들 풀이 메모용으로 작성한다.  https://www.acmicpc.net/problem/18508 18508번: Delete the PointsThe first line contains a single integer n (1 ≤ n ≤ 3000), the number of points. Each of the following n lines contains two integers xi and yi (0 ≤ xi, yi ≤ 109), describing the coordinates of the i-th point. All points are distinct.www.acmicpc.net개인적으로 굉장히 어렵다고 생각하는 문제다. 처음 봤을 때는 골드2 였지만, 현재는 플레5가 되었다. 아는 ..

A - 구현하면 됩니다 B - 뇌빼고 $A_i \in [l, r]$ 인지, 왼쪽인지 오른쪽인지 케웍을 하면 됩니다 C - $x \leq \sqrt{D}$ 까지 확인하며 $y$를 적당히 봐주면 되는데.. non-negative integers 가 0을 포함 하지 않는다는 능지이슈가... D - 점 하나를 고정하고 구간합 등으로 개수를 세주면 됩니다. E - https://cp-algorithms.com/sequences/mex.html 라이브러리 체커 문제였습니다. 간단히 요약하자면 트리셋이나 pq같은거에 현재 수열에 없는 값들을 저장해주면 mex값은 그 중 최소가 됩니다. F - 어떤 정사각형이 최소의 변 길이로 점들을 포함한다는 것은, $\max ( \max X - \min X, \max Y - \mi..

A - 구현하면 됩니다. B - 구현하면 됩니다. 오버플로우 신경쓰기 싫어서 저는 파이썬을 사용했습니다. 여담으로 1 이 입력으로 들어오는 경우를 조심해야 합니다. 저는 조심 못해서 1틀함... C - "구현"하면 됩니다. 끔찍하지만 이쁘게 짤 생각을 안하고 ctrl C + ctrl V 를 많이 하면 편합니다. D - $S_i$ 와 $T_i$ 의 값이 달라야하며, 각 값은 0 또는 1 밖에 나올 수 없습니다. 이는 조금 생각해보면 $S_i$, $T_i$를 잇는 양방향 간선이 있는 그래프가 주어졌을 때, 이분 그래프인지 판별하는 문제로 환원할 수 있습니다. $S_i = T_i$ 인 케이스만 따로 예외처리 해줍시다. E - 같은 $K$에 대해, 답에 영향을 주는 부분은 분모에 있는 합 부분입니다. 결국 $K..

https://www.acmicpc.net/problem/2419 2419번: 사수아탕 첫째 줄에 n과 m이 주어진다. 둘째 줄부터 n개의 줄에 사탕 바구니의 위치 xi가 주어진다. (0 ≤ n ≤ 300, 1 ≤ m ≤ 1,000,000, -10,000 ≤ xi ≤ 10,000) 사탕 바구니의 위치는 중복되지 않는다. www.acmicpc.net 상당히 유명한 문제이다. 인터넷을 찾아보니 다른 분들과 조금은 다른 접근을 한 것 같아 풀이를 적어본다. 우선 보자마자 드는 생각은 dp를 해야할 것 같다는 것과, $dp(l, r, k)$ = $[l, r]$까지 사탕을 먹었고, $k = 0$이면 $l$, $1$ 이면 $r$에 있을 때 정답 정도로 정의해서 계산하면 될 것 같았다. 하지만 이 방법은 다음 사탕을..

추석이고 나가도 할 건 없고.. 그럼 뭐를 해야할까? ps와 아니메 시청 말곤 없을듯.. 전희절창 심포기어가 좀 재밌어 보이던데 볼 예정이다. 매일 oi셋 돌고 업솔빙하기 라는 장대한 계획을 세웠는데.. 5시간 풀집중은 너무 힘들다. 이걸 다들 어떻게 하는걸까? 내가 늙어서 그런듯... 셋을 거하게 말아먹었다! B에서 말린게 좀 큰 것 같음... 현재 a, b, c는 풀이를 알고 a, b는 구현까지 했고 c는 구현을 해야하고 d, e는 읽어보지 않은 상태이다. 업솔빙 다 하고 자려햇는데 1시부터 모니터만 보고 있다보니 정신이 나갈 것 같아.. 나머진 내일 일어나서 하는걸로... 회복도 공부의 한 파트 아닐까? 암튼 내일은 반드시 정리해서 올리는걸로... 내일은 유사코를 돌 예정인데 그래도 이런 무서운 셋..

소녀 가극 레뷰 스타라이트 보세요. 저번 글을 쓰고 한달 정도가 되서 그동안 뭘 했는지 좀 적어볼까 한다. 일단 풀었던 인상깊은 문제들을 정리해보자면.. (개인 정리용이라 풀이가 엄밀하거나 자세하지 않음은 양해 부탁드립니다)https://www.acmicpc.net/problem/19239 19239번: min-xorFor the first min-xor(), the set is {24, 17}. The minimum bitwise xor is 24 ^ 17 = 9. For the second min-xor(), the set is {24, 17, 23, 30}. The minimum bitwise xor is 24 ^ 30 = 6 (also 17 ^ 23 = 6). For the third min-xo..

블루를 찍었다! 이번 1월부터 ps를 본격적으로 시작하며 그 때 팠던 계정인데, 학기중에 새벽코포를 할 순 없어서 유기하고 있다 방학에 다시 시작하였다. 최근에 있던 div 3 에서 6/7 솔을 하고 블루를 달성하였다. 3월에 마지막으로 후기(?)를 작성하고 뭔가 쓴 게 없어서 그동안 어떻게 살았는지, 뭘 공부하였는지도 작성해볼까 한다. 4월 4월에 있던 가장 큰 이변은 아마 ps과외를 시작했다는거다. 정올 1차 전까지만 2달 특강 느낌으로 할 계획이었다. 그냥 학교 동아리에서 주는 셋과 수업을 들으며 준비할 예정이었지만, 동아리 수업이 5월 이후에 시작하고 기초적인 내용만 다룰 예정이라는 얘기를 부장에게서 듣고, 혼자서 준비할 자신이 없어서 과외 선생님을 지인의 추천을 받아 구하였다. 과외의 형식은 문..

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에..