Problem Solving102 Codeforces Round #192 (Div. 1) A : 가로줄, 세로줄을 이분그래프로 모델링하고, 가로줄에 유량 n, 세로줄에 1만큼 준 다음에 max flow 돌려본다. 답이 안 나오면, 세로줄에 유량 n, 가로줄에 1만큼 준 다음에 max flow 돌려본다. 이래도 답 안 나오면 -1.B : 시작점에서 BFS, 도착점에서 BFSC : n이 7 이하면 모든 간선에 대해서 골라보고 아니면 1~n까지의 수열을 계속 랜덤 셔플해보면서 인접한 정점들에 대해 간선을 줌. 할 수 있는 동안 해보고 안되면 불가능 했더니 맞음. 2016. 3. 8. SRM 683 Div.1 250 : partial sum500 : gcd, lcm이 지수의 min, max를 취하는 연산이기 때문에 원래의 지수들이 보존되는 성질이 있다. 따라서 각 지수별로 차수를 정렬하고, 각 지수에서 k번째 차수인 수를 다 곱한 걸 다 더하면 답이 된다.900 : 라그랑주 보간법 2016. 3. 7. Persistent Segment Tree 1. SPOJ 'COT - Count on a tree'2. SPOJ 'MKTHNUM - K-th Number'3. Codeforces Round #140 (Div. 1) Problem E. Noble Knight's Path 2016. 2. 25. SRM 682 Div.1 300 : tonyjjw랑 나랑 푼 방법이 거의 같은데 뭔가 이상하다. 우선 중복간선은 존재하지 않는다고 입력 조건에 있음. 각각의 간선을 잘라보면서 트리의 지름을 구하듯이 어떤 점에서 가장 먼 점을 찾고 거기서 또 가장 먼 점을 찾음. 지름의 길이가 5 이상되면 답이 되는 체인이 존재한다고 했서 맞았음. O(n^2).tonyjjw를 통해서 ainu7님의 정해를 들으니 a-b-c-d-e가 있으면, a-b와 d-e를 전처리로 n^2에 구한다. 이후 b와 d 사이에 존재하는 c 후보들에 대해 a와 e랑 다른 걸 찾으면 된다고 한다. 전처리를 잘하면 전체 O(n^2)에 수행된다. 450 : 간선 하나(중복 간선은 간선 하나로 전처리) 달린 정점들 개수(C)를 카운팅하고 다음에 n-C-1 출력하니까 예제가 다 .. 2016. 2. 23. SRM 679 Div.1 250 : 그리디하게 풀린다. 밑에서부터 올라오면서 누적하고 음수되면 버리면 됨. 900 : D(i, j) : i번 가방에서는 점수 k인 카드를 쓸 때에 다른 가방에서 점수 j인 카드를 써서 좋은 수가 되는 경우의 수라 정의하자.D(i, j) = Sigma[Count(i, k) * (isGood(j+k)=='Y')]그러면 i < j일 때에 ans(i, j) = Sigma[D(i, k) * Count(j, k)]. 2016. 2. 22. 이전 1 ··· 14 15 16 17 18 19 20 21 다음
