- 링크: codeforces.com/contest/1433

오랜만에 아는 사람들과 함께 코포 버추얼을 돌려봤습니다. 힘드네요... 오랜만이라 그런가;

ABD풀고 CE는 나중에 풀어봤습니다. 전체 정확한 풀이는 SecondThread의 영상(www.youtube.com/watch?v=GUri-39QQ7s)을 봐주세요. 민트보다는 레드의 설명이 더 낫죠.

 

아래는 간략한 풀이입니다.

(A) Boring Apartments

문제처럼 1, 11, 111, 1111, 2, 22, ... 이렇게 만들면서 풀면 됩니다

 

(B) Aet Another Bookshelf

책 덩어리 안에 있는 0의 개수를 세면 됩니다. 즉 n - leading_zeros - trailing_zeros - 1의 개수 이런식으로 하면 되겠죠?

뭔가 직관적으로 감이 왔는데 증명은 잘 모르겠네요.

 

(C) Dominant Piranha

입력 크기가 전부 같으면 -1, 아니면 max값을 갖는 원소 중 왼쪽 또는 오른쪽이 그 값이랑 다른 녀석의 인덱스를 출력하면 됩니다.

참 알고 나니 쉽네요 아쉽습니다

 

(D) Districts Connection

뭔가 어려워보이지만? 어려운 문제는 아닙니다.

일단 각 도시들이 전부 같은 갱인 경우 답이 없습니다. 그 외에는 전부 답이 존재합니다.

쉽게 푸는법은 1번 도시랑 나머지 도시를 전부 연결하는데 이때 같은 갱이 아닌 도시만 연결합니다.

그러면 1번 도시와 같은 갱인 도시들이 남아있을텐데, 1번과 같은 갱이 아닌 아무 도시나 정해서 그 도시랑 전부 연결하면 됩니다.

 

(E) Two Round Dances

2n명을 반으로 나눠서 각각 강강술래를 도는 경우의 수를 구하는 문제입니다. 이때 전/후 관계는 고려하지 않고, 강강술래 돌때 1234, 2341, 3412 이런거는 다 같은 경우로 생각합니다.

문제를 대충 읽어서 참 아리송한 문제였는데 적절히 조합을 만들어주면 아래와 같은 식을 만들 수 있습니다.

\[f(2n)= {}_{2n}\mathrm{C}_{n}/2 \cdot \left( (n-1)! \right)^2 \]

일단 사람 수를 2n이라고 하겠습니다. 사람들을 두 그룹으로 나누어야 하니 2n Choose n의 경우의 수가 생깁니다. 그런데 전/후 뒤바뀌는 것은 고려하지 않는데, 예를 들어 (1, 2) / (3, 4)나 (3, 4) / (1, 2)나 동일하니 2로 나눕니다.

자 이제 각 그룹마다 강강술래 도는 순서를 정합니다. n명을 한줄로 줄세우는 경우의 수는 n!개인데, 원형이니까 n을 나눠줍니다. 그럼 (n-1)!입니다. 두 경우의 수를 곱하면 (n-1)!^2가 됩니다.

좀 뭔가 너무 복잡한거같은데..;; 아무튼 저는 이렇게 식을 만들었습니다.

 

(F, G)는 나중에 알고리즘 고수 되면 풀어보는걸로 하겠습니다.

휘유 업솔빙하고 정리하는것까지 하니 참 힘드네요. 코포는 더욱 더 가끔 해야겠습니다

반응형