http://codeforces.com/contest/618/ 졸리기도 하고 코포를 보고 싶지 않아서 제낄라고 했는데, 이름을 밝힐 수 없는 어떤 분이 자꾸 "코포봐야죠 코포안봐여?" 해서 봤다. ..아 근데 진짜 졸리긴 졸렸음. 한시간 자고 한시 반에 일어났는데 너무 일어나기 싫더라.. A 함정이 있을까봐 걱정했지만 그런거 없었다.4분 (AC) B a|b를 a||b로 써놓고 한참을 찾았다. 하... 19분 (AC) C 문제 자체는 간단하고 쉬운 기하 문제다. 각도정렬을 알면 풀이 나오는 수준. 내가 C를 락하고 열심히 hack을 시도했었는데, 다들 너무 잘짜서 아무 것도 시도하지 못했다. 하지만 정작 systest를 하니까 정말 수많은 사람들이 나가떨어졌고, 나가떨어진 사람들의 소스코드를 열심히 읽고 ..
(Different Class, 1995)
Problem : 사이클이 없는 유향 그래프 G = (V, E)가 주어졌을 때, 모든 정점을 덮는 최소 개수의 Path를 구하라.Solution : Path에 집착하면 안된다. 간선들로 풀어서 생각하자. Path 상의 간선이 X개면 N - X개의 Path로 커버 가능하니 선택된 간선의 개수를 최대화하면 된다. 간선을 최대화 할 때 제약 조건은 : 각 정점의 indegree에 선택된 간선이 오직 하나, outdegree 오직 하나인 형태로 구성되어야 한다는 것이다.이제 각 노드를 두개로 쪼개자. 하나는 indegree, 하나는 outdegree를 상징한다. 실제 그래프 상의 간선을 저 안에 잘 박아두면 이분 그래프가 생기니 이제 최대 매칭을 구한다. O(VE). https://en.wikipedia.org..
- Total
- Today
- Yesterday