구사과

프리스비 (USACO Gold 2014.12)https://www.acmicpc.net/problem/10649N이 작은 문제다. 1) 비트 DP를 한다. dp(S) = 현재 집합의 추가 가능한 스택 양 이라 정의하면, Min(dp(S\j), Pj - Sum(S\j)) 중 최대인 j를 고르면 된다. 이후 모든 부분집합 S 중에 높이 합이 H 이상인 애들에 대해서 최댓값을 고른다. 2) 그리디를 한다. 집합이 고정되어 있을때, P + W 순으로 정렬한 후 구한 Min(P + W - S) 값이 항상 가능한 순열 중 최대를 낼 수 있다는 것을 증명할 수 있다. 고로 초기에 P+W 순으로 정렬후 모든 집합에 대해서 시뮬레이션하면 된다. 이런걸 그리디로 할 때는, deadline first라는 걸 기억해두면 편한..

http://codeforces.com/contest/618/ 졸리기도 하고 코포를 보고 싶지 않아서 제낄라고 했는데, 이름을 밝힐 수 없는 어떤 분이 자꾸 "코포봐야죠 코포안봐여?" 해서 봤다. ..아 근데 진짜 졸리긴 졸렸음. 한시간 자고 한시 반에 일어났는데 너무 일어나기 싫더라.. A 함정이 있을까봐 걱정했지만 그런거 없었다.4분 (AC) B a|b를 a||b로 써놓고 한참을 찾았다. 하... 19분 (AC) C 문제 자체는 간단하고 쉬운 기하 문제다. 각도정렬을 알면 풀이 나오는 수준. 내가 C를 락하고 열심히 hack을 시도했었는데, 다들 너무 잘짜서 아무 것도 시도하지 못했다. 하지만 정작 systest를 하니까 정말 수많은 사람들이 나가떨어졌고, 나가떨어진 사람들의 소스코드를 열심히 읽고 ..

(Different Class, 1995)