https://codeforces.com/contest/1930
총평: 미친듯이 어렵네요;;;;;;; Div1+Div2 combined round기 때문에 원래 어려운 대회는 맞지만, 그래도 다른 combied 대회와 비교했을때 더 어려웠던것 같습니다.
A: 2n개를 정렬하였을 때, 1번째로 작은 수 + 3번째로 작은 수 + ... + 2n-1번째로 작은 수가 답입니다.
증명은 간단한데요, min(x,y)가 답에 더해지기 때문에 1번째로 작은 수가 무조건 답에 더해지게 되는데,
그러면 답에 더해지지 않는 수는 최대한 작은 수로 잡는게 이득입니다. 이 아이디어를 반복하면 위 값이 최대임이 쉽게 증명됩니다.
B: 값이 증가,감소,증가,감소가 반복되는 식으로 수열을 정의하면 됩니다.
예를 들어, 1 5 2 4 3 같은 경우 +4,-3,+2,-1로 증가, 감소가 반복하기 때문에 이렇게 할 경우 언제나 옳은 답이 됩니다.
증가,감소가 반복하는 수열을 만드는 방법은 간단합니다.
홀수번째는 앞에서 부터 1,2,3...을 넣고, 짝수번째는 앞에서부터 n,n-1,n-2,...을 넣으면 됩니다.
C: 여기서부터 상당히 어려워집니다; i번째 값이 실제로 S에 넣어질 때, a_i+1이상 a_i+i 이하의 원하는 값으로 항상 넣을 수 있습니다.
모든 i에 대해서 전부 그렇고, 그렇게 되도록 i를 잘 골라낼 수 있습니다. 증명은 귀납법으로 가능합니다.
그러므로, 모든 [a_i+1,a_i+i] 구간을 전부 나열하고, 값이 중첩이 되지 않도록, 최대한 다양하게 답을 고르되, lexicographically large여야 하기 때문에 가장 큰 값을 그리디하게 골라주면 됩니다. 이 과정이 꽤 어려울 수 있는데, 잘 sweeping 해주면서 찾아주면 됩니다(?)
D: 정말 상당한 관찰이 필요합니다.
먼저, 0은 그대로 0으로 두는것이 좋습니다. 이는 자명입니다. 1은 0으로 두느냐 1로 두느냐가 고민인데, 만약 0으로 두었다면 양옆중 하나는 반드시 1로 두는것이 이득입니다. 1은 01의 mode기도 하고, 양옆을 1로 두지 않을 이유가 없습니다.
더 정확히 관찰해봅시다.
만약 p=100이란 문자열이 있다고 가정합시다. 그렇다면 q=010으로 두는것이 이득입니다. 1의 개수가 똑같은데 왜 이득이냐?할 수 있는데, 1이 오른쪽에 있어야 다른 1들에 영향을 줄 가능성이 커지기 때문에 더 오른쪽에 1이 있는 이것이 이득입니다. 101의 경우도 010이 이득이고, 110,111도 010이 이득입니다. 즉, 1이 있으면 뒤에 2개가 무엇이든 상관 없이, 항상 1 1개로 mode를 만들 수 있습니다.
결국, f(p[1,2...,n])은 다음과 같이 정의 가능합니다.
만약 p[1]==0이면 f(p[2,3,...,n])이며, p[1]==1이면 f(p[4,5,...,n])+1이 됩니다. 0이 나오면 1칸 건너뛰고, 1이 나오면 3칸 건너뛴다고 보면 됩니다.
따라서 저희가 구해야 하는 값은 잘 sweeping하면서 볼 수 있습니다.
S_i = \sum_{j=i}^n f(s_i,...,s_j)로 정의합시다. 만약 p[i]==0이라면 S_i = S_{i+1}이며, p[i]==1인 경우 S_i == S_{i+3} + 3이 됩니다. i가 n에 가까워질수록 +3이 아니라 더 작은 값이 될 수 있으니 예외처리에 주의해주세요.
모든 S_i를 이제 다 더해주면 답이 됩니다. 시간복잡도는 O(n)입니다.
E: 상당히 하드한 조합론입니다.
지운 숫자를 X, 살린 숫자를 O라고 합시다. 간단한 관찰로 앞에서부터 K번째 X의 위치를 L, 뒤에서부터 k번째 X의 위치를 R이라고 합시다. 그렇다면, 다음을 전부 만족하는것과 문자열을 연산으로 만들 수 있다는 것이 동치입니다.
1) L+1<=R-1
2) 문자열의 [L+1,...,R-1]에서 X의 개수가 2k의 배수개여야 합니다. 단, O의 개수가 0개여서는 안됩니다.
이를 만족하는 문자열의 개수를 세봅시다. L과 R의 위치에 주목하면, 답은
sum_L sum_R comb(L-1,k-1) comb(R-1,k-1) ( comb(N-L-R,0) + comb(N-L-R,2k) + ... )가 됩니다.
이제 이 값을 구할때 덧셈을 재정렬 잘 하고, combination을 잘 정리해주면 됩니다;
다 건너뛰고 결과는 comb(N,0) + comb(N,2k) + comb(N,4k) + .... - comb(N-1,2k-1) - comb(N-2k-1,2k-1) - comb(N-4k-1,2k-1) - ... 가 됩니다.
계산하는데 k마다 총 O(N/k)의 시간이 필요하며 k=1,...,N이기 때문에 harmonic sum을 생각하면 총 O(klogk)의 시간에 구할 수 있습니다. combination을 O(logMAX)의 시간에 구하면 TLE가 날 수 있으므로, factorial과 1/factorial값을 미리 계산해두어서 combination을 O(1)에 구하도록 합시다.
F: 여기서부터 못풀어서 풀이를 말할수가 없네요;
G,H,I: 읽지도 않음