구사과

Soap Time (CF 118E) http://codeforces.com/contest/185/problem/E 일단 45도 돌려서 chebyshev distance로 생각하고, 지하철역이 없을 때에 대한 corner case를 처리해주자. 먼저 minsub[i] = (i번 정점에서 가장 가까운 임의의 지하철역까지의 거리) 를 정의하고, 구한 후 시작하자. 시간 제한이 넉넉하기에 아무 방법이나 썼는데, 난 2d range tree를 짠 후 parametric search를 돌리는 방식으로 O(nlg^3n)에 해결하였다. 문제 해결에 있어서는 최댓값을 최소화하기 때문에 직관적으로 parametric search가 떠오른다. parametric search를 구현하는 것이 가장 어려운 부분이다. 일단 답이..

1. 지우개 https://www.acmicpc.net/problem/11881 Solution 1 : dp[i][j] = A(a1) < A(a2) ... < A(aj) N - K개의 점을 지났다라고 정의하겠습니다. dp[i][j] = i번 점을 j번째로 지났다 라고 정의하면, 다음과 같은 점화식을 유도할 수 있습니다.dp[i][j] = Min(dp[i-1][k] + |Xj - Xk| + |Yj - Yk|) for all 1 = 2) 시간 복잡도는 O(N^3). 3. 신기한 키보드https://www.acmicpc.net/problem/1796 고정된 알파벳에 대해서 생각해보면 각각의 알파벳의 위치는 딱히 중요하지 않습니다. 'a'를 값으로 가지는 가장 왼쪽 / 오른쪽 만 찍고 오면 되니까요.dp[i][..

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=249좀 많이 입풀이라... 가려 듣길 부탁한다 ㅠㅠ D : Travel검증되지 않은 풀이다. 제대로 읽었다면 s - t, u - v를 잇는 vertex-disjoint path를 찾는 문제로, maximum flow를 짰고 틀렸다. 데이터탓이라고 정신승리후 끝냄. E : Roommate 옛날에 AC했었다. 풀이는 대충... 이랬던거 같다.dp[i][j][t1][t2] -> 지성(0번)이 i번 task까지 "완벽히" 완료했으며, 영표(1번)가 j번 task까지 "완벽히" 완료했고, t1번째 사람이 i+1 / j+1번째 task를 t2 시간동안 돌렸다.점..