Codeforces Round #412 (Div. 2) E. Prairie Partition

문제링크

모든 자연수를 \(1+2+4+.....+2^{k-1}+r\) 로 분해할 수가 있는데

M개의 수를 이 방식대로 분해하여 분해된 요소들을 모두 모아 정렬한 결과인 sequence를 A라고 해보자.

\(1\leq{N}\leq{10^5}\)

\(1\leq{a_i}\leq{10^{12}}\)

sequence의 크기 N과 N개의 elements 로 이루어진 A의 원소들 ai 가 입력으로 들어온다.

이 A를 다시 분해하기 전의 원래의 수로 복원하려고하는데 복원하는 방법은 여러가지가 있을 것이다.

복원의 결과로 나온 수가 K개일 때 K가 될 수 있는 수는 여러가지가있을 것이다. 이 때 이 가능한 K들을

오름차순으로 모두 출력하는게 문제의 질문이다.

우선 k+1 개의 수를 \(1+2+4+.....+2^{k-1}\) 의 형태로 합쳐준 것을 체인이라고 부르겠다.

여기에 r이 붙게되면 꽉찬 체인이라고 부를 것이고, r이 붙기전에는 빈 체인이라고 부르겠다.

그럼 결국 이 문제는 주어진 N개의 원소들로 하나도 남김없이 체인으로 합쳐 줄 때

몇개의 체인으로 합칠 수 있냐를 묻는 문제가 된다. 이 문제는 우선 그리디하게 풀 수 있다.

그럼 우선 문제를 구하는 방향은 이렇게 하겠다. 

빈 체인 하나를 만들고 남은 원소들을 남김없이 빈 체인들에 쑤셔 넣을 수 있는지 확인한다. 되면 답에 1을 추가한다.

빈 체인 두개를 만들고 남은 원소들을 남김없이 빈 체인들에 쑤셔 넣을 수 있는지 확인한다. 되면 답에 2를 추가한다.

빈 체인 세개를 만들고 남은 원소들을 남김없이 빈 체인들에 쑤셔 넣을 수 있는지 확인한다. 되면 답에 3을 추가한다.

........

빈 체인을 더이상 만들 수 없을 때 까지 반복한다.

그럼 답을 모두 출력하면된다. 만약 답이 없다면 -1을 출력하면 된다.

그럼 이제 빈 체인을 m개를 만들 때 어떤 기준으로 빈 체인을 만들어야 하는가, 그리고

어떤 방법으로 남은 원소들을 빈 체인들에 쑤셔 넣을 것인가 만 알면된다.

우선 빈 체인을 m개 만드는 기준은 두가지가 있다. 우선 체인의 오른쪽 끝 수(가장 큰 수)가 클수록좋다.

왜냐하면 각각의 빈 체인은 2*(끝 수) 이하인 r만 합칠 수가 있기 때문에 끝 수가 클 수록

합칠 수 있는 r의 가짓수가 많아지기 때문이다. 두번 째로 체인에 포함되는 수가 많을 수록 좋다.

왜냐하면 남은 원소들을 빈체인들에 하나씩 모두 붙여줘야되는데 이 남은 원소들이 적을 수록

빈 체인들에 남김없이 다 붙여줄 가능성이 커지기 때문이다. 그런데 예를 들어

우선 빈 체인A와 빈 체인B가 있고 체인A의 길이는 lenA, B의 길이는 lenB 라면

lenA < lenB 이면 A에 포함되는 원소들의 집합은 B에 포함되는 원소들의 집합의 진 부분집합이다.

왜냐면 빈 체인은 무조건 1로시작해서 2배씩 증가하는 연속된 숫자들로 이루어져있기 때문이다.

그렇기 때문에 하나의 빈 체인을 만들 때 가능한한 현재 남은 원소들로 만들 수 있는 가장 긴 체인을 만드는 것이

이득이라는 뜻이 된다. 그렇게 되면 끝 수도 커지면서 체인에 포함되는 수도 많아지기 때문이다.

그러면 이제 체인을 m개 만들었다면 어떻게 남은 원소들을 체인에 붙여줄까

우선 남은 원소들 중 크기가 큰 원소일 수록 붙을 수 있는 빈 체인의 후보가 적을 것이다. 왜냐하면

빈 체인의 가장 큰 원소가 커야 하기 때문이다. 그럼 남은 원소들 중 가장 큰 원소부터 끝 수가 가장 큰 

빈 체인에 우선으로 붙여나가면 될 것이다. 이 것을 코드로 어떻게 옮겨 넣을까?

한가지 유용한 사실 중 하나는 예를들어 5~8는 끝 수가 4이상인 빈 체인에만 붙을 수가 있기 때문에

끝 수가 큰 빈 체인부터 내려오면서 끝 수가 4인 빈 체인의 수까지 누적해왔다면

2까지 왔을 때 현재 가지고 있는 빈 체인의 수 보다 남은 수 중 5~8의 개수의 합이 더 많다면

지금 의 m에 대해 m개의 꽉 찬 체인은 만들 수가 없다는 뜻이 되고, 결과적으로

입력으로 주어진 sequence 는 m개의 수를 분해해서는 나올 수 없는 sequence 라는 말이 된다.

끝 수가 1인 빈 체인까지 이걸 반복하여 방금 말한 것처럼 사용가능한 빈체인의 수가 부족한 상황이 발생하지 않는다면

m개의 꽉찬 체인을 만들 수 있다는 것이다. 이걸 위에서 말했던 것처럼 빈 체인을 만들 수 없을 때까지 반복하면 된다. 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
int N;
ll A[100003];
int rs[53];
int chunk[53];
int pow2[53];
 
int main() {
    scanf("%d",&N);
    for(int i = 0 ; i < N; i++){
        scanf("%lld",&A[i]);
        ll a = A[i];
        int cnt = -1;
        for(ll b = a; b ; b/=2) cnt++;
        if(a == (a&-a)) pow2[cnt]++;
        else rs[cnt]++;
    }
 
    vector<int> ans;
 
    int cnt = 0;
    while(pow2[0]){
        cnt++;
        int pos = 0;
        while(pow2[pos]) pow2[pos++]--;
        chunk[pos-1]++;
 
        int now = 0;
        int ok = 1;
        for(int i = 50; i >= 0 ; i--){
            now += chunk[i];
            now -= pow2[i+1] + rs[i];
            
            if(now < 0){
                ok = 0;
                break;
            }
        }
        if(now - pow2[0] < 0) continue;
        if(ok) ans.push_back(cnt);
    }
    if(ans.size()==0) return !printf("-1");
    for(int i = 0 ; i < ans.size(); i++) printf("%d ",ans[i]);
    return 0;
}