E869120 and Constructing Array 3 [yukicoder No.689] - はまやんはまやんはまやん

考察

1. とりあえず最大ケースを考える
2. N≦250でK≦10^4なので、N=sqrt(K)くらいになっていて2乗を使うアレではなさそう
3. なるべく簡単なアルゴリズムを目指すように構築ルールを考えてみる
4. 方針「少ない種類の数で構築する」
5. 4,9,6,11を使えば前半と後半で別々に組を数えることができる
6. 4をc4個、9をc9個用意すればc4*c9組作れる
7. 合成数の和で0～10^4が作れるんじゃないかという予想
8. やってみるとAC

解法

https://yukicoder.me/submissions/258973

前半を4と9、後半を6と11を使って和が素数であるものの組を作る。
前半の4の個数をc4, 9の個数をc9とすると、和が素数の組はc4*c9通り作れる。
要は、以下の条件を満たせばいい

c4*c9+c6*c11=K
1≦c4+c9+c6+c11≦250

これはc4,c9,c6を全探索することで実現できる。
O(N^3)なので間に合う。

int K;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> K;

    rep(c4, 0, 251) rep(c9, 0, 251) rep(c6, 0, 251) {
        int d = K - c4 * c9;
        if ((0 < c6 and 0 < d and d % c6 == 0) or d == 0) {
            int c11 = d / c6;
            int n = c4 + c9 + c6 + c11;
            if (1 <= n and n <= 250) {
                vector<int> ans;
                rep(i, 0, c4) ans.push_back(4);
                rep(i, 0, c9) ans.push_back(9);
                rep(i, 0, c6) ans.push_back(6);
                rep(i, 0, c11) ans.push_back(11);

                printf("%d\n", n);
                rep(i, 0, n) {
                    if (i) printf(" ");
                    printf("%d", ans[i]);
                }
                printf("\n");
                return;
            }
        }
    }
}