E869120 and Constructing Array 2 [yukicoder No.688] - はまやんはまやんはまやん

考察

1. 制約の黒字が気になる「ただし, Kは条件を満たす数列が存在するものであることが保証される」
2. これはKによっては存在しないということ？
3. 取りうるKの値が10^9通りよりも少ないということなので、ここを全探索できるのでは？
4. 数列の順番は合計が2となる選び方に影響しないので、0と1の個数だけ関係がある
5. これは全探索できる

解法

https://yukicoder.me/submissions/258626

選んだ数の合計が2となるような選び方は、0の個数と1の個数からしか影響を受けないので、選び方を全探索しよう。
もう少し具体的には数列の0の個数と1の個数を全探索する。
0の個数がc0個、1の個数がc1個ならば、選んだ数の合計が2となる選び方は、C(c1,2)*2^c0通りある。
C(a,b)は二項係数。
よってC(c1,2)*2^c0がKである場合を見つけたらそれを答えればいい。

ll d[31];
int K;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> K;

    d[0] = 1;
    rep(i, 1, 31) d[i] = d[i - 1] * 2;

    rep(c0, 0, 31) rep(c1, 0, 31) if(1 <= c0 + c1 and c0 + c1 <= 30) {
        ll k = 1LL * c1 * (c1 - 1) / 2 * d[c0];
        if (K == k) {
            int N = c0 + c1;
            printf("%d\n", N);
            vector<int> ans;
            rep(i, 0, c0) ans.push_back(0);
            rep(i, 0, c1) ans.push_back(1);
            rep(i, 0, N) {
                if (i) printf(" ");
                printf("%d", ans[i]);
            }
            printf("\n");
            return;
        }
    }
}