https://codeforces.com/contest/1926
총평: div4라 진짜 쉬운 라운드긴 한데...................... 솔직히 제가 지금까지 본 div4중 제일 어렵네요 -_-
A: A와 B중 가장 많은 문자를 세면 됩니다. 하나하나 개수 세도 OK고, 여기는 하나 트릭을 설명해주려 합니다.
그냥 정렬해준뒤 가장 가운데 문자 출력해주면 됩니다. 이러면 문자 개수 하나하나 셀 필요 없어서 코딩이 초 간단해집니다.
B: 행 하나를 전부 봅시다. 만약 1이 정확히 1개만 있다면 삼각형, 아니면 사각형입니다.
C: 봐야하는 숫자가 20개밖에 안되기 때문에 1~20만 모든 숫자에 대해서 각자리 숫자 합을 미리 계산하고 누적합을 미리 계산해두면 됩니다.
이제 n이 주어질때마다 n번째 누적합을 출력하면 끝
D: 두 수의 합이 2147483647이 되는 것들을 묶고, 총 묶은 쌍 + 안묶인 숫자 개수를 출력해주면 됩니다.
간단하게 세는 방법은 모든 숫자를 map에 넣고, 모든 a_i를 보면서, map에 2147483647-a_i가 있는 i의 개수를 cnt라고 했을때,
n-cnt/2가 답이됩니다.
E: 약간 생각이 필요합니다.
f(n,k) = 위 규칙대로 하였을 때 나오는 답이라고 정의합시다.
만약, k <= (n+1)/2라면 답은 2k-1이됩니다.
만약, k > (n+1)/2라면 답은 2*f(n/2,k-(n+1)/2)가 됩니다.
함수를 부를수록 n이 절반으로 떨어지기 때문에 총 f의 호출수는 O(logn)이 되며, 그러므로 f(n,k)는 O(logn) 시간에 계산할 수 있습니다.
F: 어렵습니다;;;;;;;;;;;
테두리는 지울 필요가 없으므로 지워야 하는건 가운데 5x5칸, 총 25칸입니다.
체스판처럼 생각했을때 흑칸과 백칸은 독립적이므로, 흑칸과 백칸을 따로 생각해줍시다.
그러면 12칸, 13칸 따로 생각하면 되는데 칸 수가 충분히 적기 때문에 2^12, 2^13가지를 bit DP로 계산해주면 됩니다.
G: C를 적당히 S나 P로 할당해줍시다. 그렇다면, 정답은 S-P 형태의 edge의 개수가 됩니다.
증명은 자명합니다. S-S나 P-P 사이에서는 edge를 세울 이유가 없고, S-P 사이에는 반드시 세워야하기 때문입니다.
그러므로, 트리 DP를 이용하여 S-P의 개수를 세줍시다.
f(v,state) = v를 subtree로 하는 tree를 볼 때, 부모의 state가 S 혹은 P일때 S-P edge의 개수로 정의해줍시다.
만약 v가 C라면 S 혹은 P로 할당해줘서 state와 v가 다르면 답에 +1을 해주고, S나 P중에 min을 return해줍니다.
그 외라면 무조건 S 혹은 P로 할당해줘서 계산해주면 됩니다.
