구사과

https://www.acmicpc.net/problem/8128증명에 증명을 더해가면서 시간 복잡도를 줄이는 스타일의 그리디였는데 재밌었다. 일단 먼저 N^2 알고리즘을 목표로 시작해보자. 가장 많은 역을 덮는 지하철 노선의 집합을 최적 집합이라고 한다. Lemma 1. 최적 집합의 모든 끝점을 리프로 변형시킬 수 있다.증명 : 그렇지 않은 최적 집합이 존재한다면 이를 두고 생각해 보자. 만약에 현재 끝점이 리프가 아니면, degree가 2 이상이라 빠져나갈 구멍이 하나 존재한다. 이 구멍으로 경로의 길이를 증가시켜나가면 답을 감소시키지 않으면서 한쪽을 리프로 만들어 줄 수 있다. Lemma 2. 최적 집합에 덮인 지하철역이 서브트리를 이루게 변형시킬 수 있다. (이 때 서브트리는 subgraph로써의..

ICPC 월드 파이널 2017 주간이 다가와서 최근 옛날 기출문제를 풀어보고 있다. World Finals 2008도 opencup 팀연습으로 돌았었는데, 문제가 좋다는 느낌은 안 들었다. 특히 어려운 문제들이 찍어 맞춰라 / 단순 코딩 지옥이라 불만족스러웠음.이번 ICPC에서 한국 팀들의 성적이 그 전과 비교가 안 될 정도로 우수하다. 어느 정도 훌륭할 것이라고 예상은 했지만 이 정도일 것이라고 예상한 사람은 아무도 없었을 것이다. 팀원들이 대부분 젊은데, 앞으로도 많은 활약을 기대해 본다. 2011 G. Magic Sticks일단 모든 막대기를 사용해야 하는 상황이라고 가정해보자. 넓이를 최대화하려면 모든 정점을 원 위에 뿌려주는 것이 최선이다. 직관적으로 그럴듯 해 보이긴 하는데 증명은 음.. 암튼..