SRM 681 Div.1
300 : 정점을 압축하고 Parametric Search 하면서 Maximum Flow 돌리면 됨. 구간을 나타내는 정점을 압축할 때 구간의 경계는 분리해서 압축해야함. 예를 들어서, [L(1), R(1)], [R(1)=L(2), R(2)], ... [R(k-1)=L(k) R(k)]는 [L(1), L(1)], (L(1), R(1)), [R(1), R(1)], (R(1)=L(2), R(2)), [R(2), R(2)] ... 이런식으로. 그리디 해법이 있다는데 생각해보아야함. 500 : 가운데부터 넓혀나가면 됨. 메모리 제한이 빡빡해서 배열 별도로 잡으면 안되고, left right 포인터 2개 잡아서 하면 됨. N^2 같아보이지만, (i, X(i)) 점들을 좌표평면에서 생각하면 언덕 모양들이 나올 때에 ..
2016. 2. 19.
BOJ 11928 공기놀이
문제 링크 : https://www.acmicpc.net/problem/11928(1) n이 홀수인 경우의 답은 이 되고, (2) n이 짝수인 경우의 답은 가 된다.먼저 (1)의 풀이를 살펴보자. 편의를 위해 R을 빨간 돌, B를 파란 돌이라 하자.R이 B의 왼쪽에 있는 게 홀수 개인 가짓수를 세아리자. R을 n개와 B를 n개 늘어놓은 것 중 하나를 a라 하고, 그걸 거꾸로 나열한 걸 b라 하자. 그러면 a에서 (R,B)의 개수는 b에서 (B,R)의 개수와 같고, 즉 a,b에서의 (R,B)의 개수의 합은 a에서의 (R,B)와 (B,R)의 개수를 세는 것이 된다. 이는 R 중 하나, B 중 하나를 택하기만 하면 되므로 총 개로 홀수이다. 따라서 a에서 (R,B)의 개수가 홀수였다면 b는 짝수이고, a가 짝..
2016. 2. 10.
