Algoogle

Algorithm for Programming Contest

Codeforces 286E Ladies’ Shop

Category: Codeforces Tag: fft, math

Ladies’ Shop

問題概要


それぞれ重さがaiのn個のバッグがある. 今そのバッグに入れる品物の種類を以下のように決めたい.

  • 全てのバッグに対して, ちょうど重さの和がそのバッグの重さと等しくなるように品物をとってこれる. ただし選ぶ品物は何種類でもよくて, さらにそれぞれの種類を複数持ってくることもできる.
  • 重さの総和が1以上m以下になるように品物を任意種類, 任意個取ってくるとその重さの総和は必ずいずれかのバッグの重さと必ず一致する.
  • これらを満たすときの品物の種類の数が最小になるもの

解法


重さを次数とした多項式fを考える. fの各項の係数をその項の次数のバッグの重さが存在するかどうかとする.
このfを2乗すると, 各係数はバッグの重さから重複を許してちょうど2個選んだときの各重さの順列になる.
なんとなく例としてサンプル1でみてみる.

1
2
3
weight: 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
f     : 0  0  0  0  0  1  1  1  1  1  1  0  0  0  0  0  0  0  0  0  0
f^2   : 0  0  0  0  0  0  0  0  0  0  1  2  3  4  5  6  5  4  3  2  1

このf^2より, 品物を2個選んだときにできる重さがわかるのでfと比較して答えを出せる.

以降はm以下の重さについて

fにあって, f^2にない品物について
3個以上選んでもその重さは明らかに存在し得ない.
よって条件から必ず必要.

f^2にあってfにない品物について
条件を満たさないので明らかにNO.
3個以上とか関係ない.

どちらにもある場合はその品物を選ぶ必要はない(それ以下の重さで作れるということなので)

どちらにもない場合について
バッグの重さの最大の2倍までは1個でも2個で作れないならどうやっても作ることが出来ないので無視
2倍より大きい場合, 最低でも3個使っていて, 2個では作れない数になっている.
2個では作れないので, それらを2つの塊に分けたら少なくともどちらかのの重さの和はバッグの重さの最大を超えているはず.
そのような場合は条件から除外されなければならず, その除外は現在の重さより前に行われる.
よってこの場合も無視してよい.

以上から答えの集合はfにあってf^2にないものが必要十分であるとわかり, そのような集合の要素は上でNOでないなら必ず1つ以上存在する.
重さが最大で10^6あり愚直に積を求めるとO(N^2)でTLEするので, FFTでO(NlogN)に落として計算することにする.

コード


(286E.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (a); i < int(b); i++)
#define rep(i,a) repi(i,0,a)
#define pb push_back
const double pi = acos(-1.0);
const double eps = 1e-5;
const int MAX = 1<<21;
typedef complex<double> cd;

void fft(cd f[], int N, bool inv){
    int n;
    for(n=0;;n++) if(N == (1<<n)) break;
    rep(m,N){
        int m2 = 0;
        rep(i,n) if(m&(1<<i)) m2 |= (1<<(n-1-i));
        if(m < m2) swap(f[m], f[m2]);
    }

    for(int t=1;t<N;t*=2){
        double theta = acos(-1.0) / t;
        cd w(cos(theta), sin(theta));
        if(inv) w = cd(cos(theta), -sin(theta));
        for(int i=0;i<N;i+=2*t){
            cd power(1.0, 0.0);
            rep(j,t){
                cd tmp1 = f[i+j] + f[i+t+j] * power;
                cd tmp2 = f[i+j] - f[i+t+j] * power;
                f[i+j] = tmp1;
                f[i+t+j] = tmp2;
                power = power * w;
            }
        }
    }
}

int a[MAX], n, m;
cd b[MAX];
vector<int> ans;

void solve(){
    int N = 1,M = m+1;
    while(N < 2*M) N <<= 1;
    fft(b,N,0);
    rep(i,N) b[i] *= b[i];
    fft(b,N,1);
    rep(i,N) b[i] /= N;
    rep(i,M) {
        if(!a[i] and (b[i].real() > 1-eps)) { puts("NO"); return;}
        if(a[i] and (b[i].real() < eps)) ans.pb(i);
    }
    puts("YES");
    cout << ans.size() << endl;
    rep(i,(int)ans.size()) cout << ans[i] << " ";
    cout << endl;
}

void input(){
    cin >> n >> m;
    rep(i,n){
        int x; cin >> x;
        a[x] = 1; b[x] = cd(1.,0);
    }
}

int main(){
    input();
    solve();
    return 0;
}

Comments