구사과

[5/13 초본, 5/27 L 추가, 5/28 M 추가, 6/22 I,J 추가, 6/23 N,T 추가] 흔한 DP 컨테스트라고 말은 하지만, 어렵다.http://tdpc.contest.atcoder.jp/ ASubset Sum이라는 유명한 문제로, 풀이 역시 유명하다. 개행 문자를 넣어야만 AC가 되니 유의.cpp : http://codepad.org/nKJbfaBR Cwin[player][i] 를 i번째 라운드까지 진행되었을 때 player의 승률이라 정의하자. 동적 테이블을 채울 때, 각 플레이어가 i-1번째 라운드를 통과하고 본인과 대전할 확률을 구할 수 있으며, 싸워서 이길 확률은 식으로 주어져 있다. 이를 통해서 테이블을 채울 수 있으며 1초 안에 통과될 만큼 시간복잡도가 나올 듯 하다. 사실 ..

http://codeforces.com/blog/entry/18009?#comment-232968이번에 ALREADY HAVE DONE이라는 팀으로 참가해서 전체 62등, Secondary 9등으로 마무리지었다. 탑텐에 떴으니 만족함 ㅎㅎ그냥 문제 수기 쓰고 정리하려고 한다. 정리해보니 내가 이렇게 심하게 버스를 탔다는 것을 다시 한번 느낌 (...) A : 쉬운 그리디가 존재한다. 내가 짰고 금방 풀었다.B : 욕하는 문제인데 난 초기에 여기서 완전 말렸다 ㅠㅠ m^3개의 가능성이 존재하는데, 일단 이 중 m^2 쌍을 precomputing하고, 쿼리당 O(m) 번 brute forcing하면 딱 시간 안에 나오는 문제다. 되게 열심히 체크하고 깔끔히 짰는데 아주 기본적인 부분에서 틀리고 완전 말림. ..

https://www.acmicpc.net/problem/1200 Naive하게 하면 (n-1)Cr * (m-1)Cs 정도의 시간에 풀 수 있으며 당연히 TLE가 난다. ( 상한이 O(2^(n+m) 이다.) 그럼에도 n과 m이 작은 편이라 지수를 하나 정도만 날려도 될 거 같은 범위이다.. 실제로 그렇고. 일단 한가지 축으로 배열을 미리 잘라놓고 생각을 하면, 이는 여러개의 1차원 배열을 자르는 문제로 환원이 된다. 배열은 (s+1)개 나올 것이며, 이를 구간 [1,a1] , [a1+1,a2] ... [as+1,n] 으로 자르는 것이라고 생각하면, Max(1