구사과

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

https://www.acmicpc.net/problem/10454 Observation 1. 모든 정점을 포함하는 최소의 직사각형을 가정하자. 이를 세 정사각형으로 채울 때, 세 정사각형 중 하나는 그 직사각형의 모서리를 모서리로 가지고 있다.-> 그렇지 않게 정사각형을 열심히 그려보면 (...) 알 수 있다. 케이스를 많이 나누는 식으로 증명이 되지 않을까.. 싶다. Observation 2. 모든 정점을 포함하는 최소의 직사각형을 가정하자. 이를 두 정사각형으로 채울 때, 두 정사각형 중 하나는 그 직사각형의 모서리를 모서리로 가지고 있다.-> 역시 그렇지 않게 정사각형을 열심히 그려보면 (...) 알 수 있다. Observation 3. X가 3SQ-sufficient 일때 X+1은 3SQ-suf..