구사과

총평I를 못풀어서 어쩌나 했는데 그거 빼고 다 풀어서 다행이다. 말린거 같았는데 생각보다 나쁘지 않았음 Short Diary (스포일러 주의) A (0:34 +1)(hyea) 처음과 끝 조건을 잘 보자, 실수를 쓰면 풀리는 문제지만 BigInteger를 쓰는게 안정적인것 같다 B (4:09)(alex9801) Yet another ant problem. 개미에 색깔이 추가되었지만, 어렵지 않게 풀 수 있다.(koosaga) 기본적으로 원에 올려놓은 개미 문제. 일반적인 개미 문제랑 관찰이 크게 다르지 않다. 사실 원이라서 엄청 헷갈렸는데 민규가 많이 도와줬다. C (1:44)(hyea) 적당한 관찰을 하면 풀 수 있는 문제이다. 숫자가 작아서 DB를 만들어도 된다. D (2:47 +3)(hyea) 수식을..

(2017.10.06 초판)(2017.10.07 Weeping Fig 문제의 해설을 보완해서 다시 작성했다.) 전대프연 2016. 분단의 슬픔최소 비용을 구하고자 한다 -> min cut과 최소 비용이 동치임을 찾는다 -> min cut으로 풀린다 류의 문제 중에서 제일 쉬운 것 같다. 이유는 간단하다. 그런 문제는 보통 풀 수 없거든source와 sink를 만들고, 그 사이에 사람들을 정점과 간선으로 적절히 이어서, source쪽 cut에 속한 정점을 A 진영 / 그렇지 않은 정점을 B 진영으로 둘 것이다. 방법은 간단하다. Min cut에 속하는 정점 집합을 $S$라 하고, 그렇지 않은 정점 집합을 $T = V\setminus S$ 라 하면, * 무조건 $S$에 들어가는 정점은 source와 $\in..

[2016.11.02 초판][2017.10.05 트리와 쿼리 7/11 추가]https://www.acmicpc.net/contest/scoreboard/195 시간이 남을때마다 하긴 했는데... 너무 힘든 연습이었다 ㅠㅠ 아주 간략하게 풀이를 설명한다. 트리와 쿼리 2 Sparse table로 level ancestor를 빠르게 구할 줄 안다면, 간단한 케이스 분석으로 풀 수 있다. 트리와 쿼리 1 / 3 Heavy Light Decomposition으로 풀 수 있다. 1번의 경우 range max segment tree, 3번의 경우 std::set으로 해결 가능하다. 어렵지 않고 개념도 유용하니 모른다면 배워보자. https://blog.anudeep2011.com/heavy-light-decompo..