구사과

http://oj.uz/problems/view/JOI14_constellation2삼각형 하나를 잡고 나머지 삼각형을 빠르게 세는..? 류의 방법으로 계속 시도를 해봤는데 진전이 별로 없었다. 실제 풀이는 굉장히 중요한 2개의 lemma에 의존하는데, * 1. 교차하지 않는 삼각형 쌍에 대해서, 두 삼각형을 완전히 분리시키는 직선이 항상 존재한다. * 2. 교차하지 않는 삼각형 쌍에 대해서, 삼각형 1의 점 - 삼각형 2의 점을 잇는 두 직선을 고려해 보자. (경우의 수는 9개). 이 중 두 삼각형을 완전히 분리시키는 직선이 항상 2개 존재한다. Lemma 1이 상당히 감명깊었다. 삼각형 쌍을 분리하는 법을 깔끔하게 정의한 것도 그렇고, (자명하지 않은) Lemma 2와 엮어서 실제로 문제를 깔끔하게 ..

A 솔직히 5분도 너무 오래 걸린것 같다..5분 pretest pass. AC+ : 결국 어떤 문자열 S, T가 있을 때 S를 적당히 rotate해서 T로 만들 수 있느냐를 묻는 문제였다. 계속반에서 비슷한 문제 (기하 문제였다) 를 KMP로 푸는 사람들이 꽤 있었는데, KMP에 숙달되었거나 라이브러리가 있는게 아닌 한, 시간 버리고 점수 와장창 까이기 딱 좋은 방법이다. 적당한 기준 원소를 아무거나 잡고 (난 std::min_element 를 사용했다.) 그쪽을 기준으로 rotate하는 것이 가장 좋은 방법이라고 생각. stl 떡칠시 아주 빠르게 짤 수 있다. 특히 std::rotate가 꿀. 난 문제를 너무 대충 생각해서 코딩 + 시간이 살짝 말린 채로 시작했고 그 부분이 아쉽다고 생각한다. (다행이..

https://www.acmicpc.net/problem/2795딱 봐도 NP-hard같은 문제를 N = 100을 주고 출제한걸 보니 당황하지 않을 수가 없었다. 일단 유일하게 생각해 볼수 있을 만한 접근법은 http://koistudy.net/?mid=prob_page&NO=369 와 같은 류의 바이토닉 기반 DP인거 같다. 한번 그 점을 생각해보고 어떠한 식으로 DP를 짜야지 최적 경로를 고려하는 점화관계를 이끌어낼 수 있는지 알아보자. 일단 생각을 쉽게 하기 위해서 1 -> 2로 가는 임의의 경로를 고정시키고, 그 경로상에서 2 -> 1로 오는 경로를 그려놓았다.#1 같은 경우에는 그냥 플로이드 한번에 풀릴 거고#2 같은 경우에는 위 링크건 문제를 풀어봤다면 그렇게 어렵지 않다. 다음과 같이 dp를..