Codeforces Round #538 (Div . 2)

https://codeforces.com/contest/1114/problem/B
https://codeforces.com/blog/entry/65136

이번 라운드에서도 처참히 깨졌다.
A도 매우 쉬운 문제였는데, 내가 맘에 안들게 풀렸고.
B번부터 아무것도 풀지도 못했다.

이 포스트에 문제를 하나씩 정리해나가고 싶다. 문제 풀면서 다시 공부하는 것이니까.

B 문제는 배열에 여러가지 수가 주어졌을 때, 그 배열을
k개의 subarray로 나누는데, 그 subarray가 m개 이상이여야 한다.
subarray는 연속하는 배열 인덱스로만 구성된다.
그리고 그 subarray에서 m개의 가장 큰 수들을 합한다.
각 subarray의 m개의 가장 큰 수의 합은 beauty라고 정의한다.

문제에서 요구하는 것은 그 모든 beauty가 최대값이 되도록하게 하는 optimal partition과
그 때의 index를 요구한다.

나는 처음에 이것을 풀기위해, 직접 파티션을 나누는 것으로 생각했다. 하지만, 그게 아니였다. 이전에 대회에서도 B를 못풀었는데 이런 부분에서 나뉘는 것 같다. 수학적 사고력을 이용해서 B 문제를 보통 풀어나가는 것 같다. 직접 문제에서 요구하는대로 하기 보다는, 이 수학적 특성을 이용하여 문제를 풀어내는 것이다.

그래서 이것을 어떻게 하냐면,
최대값이 되도록하게 만든다면 어쨋든 전체에서 m * k개의 최대값만 고르면된다.
왜냐하면 그렇게 partition이 되어야 optimal partition의 각 beauty의 sum이 최대가 되니까

그래서 그 배열을 정렬해서 m * k개 까지의 최대값만 골라내서 합한다.
그게 각 beauty의 합이 최대가 되는 값이다.

이제 index를 나누어야 하는데, 그 beauty의 합을 구할 때, index vector를 만들어서, 그 index들을 vector에 하나씩 넣는다. 그리고 정렬을 한다. 그러면 작은 인덱스에서 큰 인덱스로 정렬이 될 것이다. 이 때, 각 subarray는 m개 이상이여야 하고, 맨 마지막 인덱스는 정렬할 필요가 없다. 그래서  그 인덱스 배열에서 m개씩 뽑으면 반드시 m개이상이 된다. 뭉쳐있어서 큰 것이 다 m일수도 있고, 중간에 띄엄띄엄 있어도, m개 이상이 된다. 그리고 이미 k - 1개를 뽑아 놨으니 상관없다.

그래서

for(int i = 0; i < k - 1; ++i) division[i] = ind[(i + 1) * m - 1];
를 통해 그 index들을 구한다.

C문제는 읽고나서 손도 잘 못대었다. 너무나 큰 수들, 그리고 팩토리얼 연산을 다뤄야하기 때문에 어떻게 이것들을 처리할 수 있을지 몰랐다. C번이후 부터 약간 수학적인 내용이 코드포스에서 주로 나오는 거 같다.

문제는 다음과 같다. n과 b가 주어지는데, n!를 b진수로 나타내어서 연속하는 0의 개수를 찾는 것이다.

이 문제는 소인수 분해의 특성을 이해해야 한다.

n! = d1b^k-1 + ... dkb^0 이기 때문에
우리는 n!이 b^r로 나눠지는 최대 r을 찾아야 한다.

소인수 분해에 의해, b = p_1^(y_1) ... p_m^(y_m) 이 된다.
비슷한 방식으로, n! = p_1^(x_1) .... p_m^ * Q (x_m) 이다. (Q는 위의 보인 어떤 p_i와 서로소가 된다).

p1 .. p_n, y_1 ... y_m을 찾는 과정은 b값의 일반적인 소인수 분해로 처리될 수 있다.

x_1 ... x_m을 찾는 과정은 (n!)로 파생되는 정수가 직접 분해하기에 너무 크기 때문에 더 까다롭다. 그러나, factorial 특징들은 우리에게 다른 접근법을 준다: 각 p_i에 대해, 우리는 다음의 것을 할 수 있다:

• 초기에 x_i = 0이라고 가정한다.
• 다음의 것을 반복적으로 한다 : x_i에 floor(n / p_i)를 더하고, n을 p_i로 나눈다. 그 loop는 n이 zero일 때 끝난다.

결국에 우리는 다음과 같은 최종 r 값을 얻을 수 있다: r = min(ceil(x_i / y_i) | i in [1, m])