[Codeforces] Round #485 (Div. 1)

http://codeforces.com/contest/986

A,B는 적당히 쉽고 C,D,E,F가 헬이어서 A, B만 신속하게 풀어냈어도 100~200위 권을 할 수 있었습니다. 그런데 시험을 치룰 때 무슨 생각이었는지 A를 굉장히 이상하게 풀어서 System test에서 나갔습니다. B도 실수로 2번 틀리고 Accepted 됐습니다.

A - Fair

D[i][j]를 i번째 점에서 j번째 굿즈를 가질 수 있는 최소 비용이라고 하면, D[i][A[i]] = 0임은 자명합니다. 이제 (1, a1), (2, a2), .. , (N,aN)으로부터 시작해 BFS를 돌리면 O((N+M)*K)로 해결할 수 있습니다.

https://github.com/blisstoner/Codeforces/blob/master/Round%20485%20Div.%201/A.cpp

B - Petr and Permutations

Graph Theory의 permutation, cycle 부분을 이해하고 있어야 풀 수 있습니다. Permutation을 길이 2짜리 cycle의 곱으로 나타낼 수 있고, 이 때 길이 2짜리 cycle의 갯수의 홀짝성은 늘 유지가 됩니다. 그렇기에 주어진 permutation을 만들기 위해 필요한 2-cycle의 갯수를 우선 inversion 혹은 cycle decomposition으로 구한 후 그것을 2로 나눈 나머지와 N을 2로 나눈 나머지를 비교하면 됩니다. N을 2로 나눈 나머지와 비교하지 않고 그냥 1 혹은 0과 비교해서 1번 틀리고 또 UM_mik로 출력해서 1번 틀렸네요. 

https://github.com/blisstoner/Codeforces/blob/master/Round%20485%20Div.%201/B.cpp

A번을 완전 이상하게 떠올린게 좀 많이 아쉽네요. 학기 중이라 알고리즘에만 전념할 수가 없는 것도 많이 아쉽습니다.