WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #171 Div2 D "The Minimum Number of Variables"

問題

N個の正の整数を持つ配列A(1),A(2),A(3),...A(N)がある。
この配列の中に同じ数値は2つとない。

この配列を使って以下の操作をする、
まずA(1)を変数に代入する。
それからA(2)からA(N)までは以下のようにする。
A(i)の時、
2つの変数(2つとも同じ変数でも良い)を足して、A(i)にして、
A(i)を変数に代入する。

この操作を完了させる時、最低でも何個の変数が必要かを返せ。
この操作が完了できない場合は-1を返せ。

例)
A = 1 2 3 6 8
まず1を変数v1に代入
v1 + v1で2にしてv2に代入
v1 + v2で3にしてv1に代入
v1 + v1で6にしてv1に代入
v1 + v2で8にしてv1に代入
とすれば変数が2つあればよいから2を返す

A = 3 6 5
5はどうやっても作れないから-1を返す

A = 1 2 4 8 16 32 64 128 256
変数は1つだけでよいから1を返す
制約

1 <= N <= 23
1 <= A(i) <= 10^9

考えた事

simezi_tanさんの記事を参考にしたら分かりました。

インデックスiの値が変数に残ってたら1、そうでなければ0としたビットを持つ。
dp[bit] := A(i)までを処理し、変数がbitの時の、使用した変数の最小の数とする。
このbitの変数でA(i+1)の値が作れるならば、
以下のような更新が出来る。

  • 変数を代入する時に新しく変数を使用する場合

baseBit = bitのi+1番目を1にしたもの
dp[baseBit] = min( dp[bit] + 1, dp[baseBit] )

  • 変数を代入する時に上書きする場合

newBit = baseBitから消す変数を0にしたもの
dp[newBit] = min( dp[bit], dp[newBit] )

例)
一番上のSample
値  1 2 3 6 8
bit 1 0 0 0 0 = 1(初期状態)

A(1)で更新
値  1 2 3 6 8
bit 0 1 0 0 0 = 1 (次は更新できない)
    1 0 0 0 0 = 1 (次は更新できない)
    1 1 0 0 0 = 2

A(2)で更新
値  1 2 3 6 8
bit 0 1 1 0 0 = 2
    1 0 1 0 0 = 2
    1 1 1 0 0 = 3

A(3)で更新
値  1 2 3 6 8
bit 0 0 1 1 0 = 2 (次は更新できない)
    0 1 0 1 0 = 2
    0 1 1 1 0 = 3
    1 0 0 1 0 = 2 (次は更新できない)
    1 0 1 1 0 = 3 (次は更新できない)
    1 1 0 1 0 = 3
    1 1 1 1 0 = 4

A(4)で更新
値  1 2 3 6 8
bit 0 0 0 1 1 = 2 (最小)
    0 1 0 0 1 = 2 (最小)
    0 1 0 1 1 = 3
    0 0 1 1 1 = 3
    0 1 1 0 1 = 3
    0 1 1 1 1 = 4
    1 0 0 1 1 = 3
    1 1 0 0 1 = 3
    1 0 1 1 1 = 4
    1 1 0 1 1 = 4
    1 1 1 0 1 = 4
    1 1 1 1 1 = 5

2番目のSample
値  3 6 5
bit 1 0 0 = 1 (初期状態)

A(1)で更新
値  3 6 5
bit 0 1 0 = 1 (次は更新できない)
    1 0 0 = 1 (次は更新できない)
    1 1 0 = 2 (次は更新できない)

値5が1のbitは全てINFのままで終わる

A(i+1)の値が作れるかはsimezi_tanさんの記事にあるように、
前計算しておけばN回で済む。

i(状態数23)とbit(状態数2^23)の2重ループは、
実質2^23だけしか回らないことが分かる。
それぞれで値を作れるかでN回、どれを消すかでN回かかるので、
計算量はO(2^N*N)となる。


うーん、難しい・・・

ソースコード
const int INF = INT_MAX;
const int MAX_N = 23;

int N;
int arr[MAX_N];
int dp[1<<MAX_N];
int p[MAX_N][MAX_N]; // p[k][i] = j : A(k) = A(i) + A(j)

// A(k)をmaskの変数状況で作れるかを返す
bool canCreate( int k, int mask ){
    for( int i = 0; i < N; i++ ){
        if( ((mask >> i) & 1 ) == 0 ) continue;
        int j = p[k][i];
        if( j == -1 ) continue;
        if( ((mask >> j) & 1) == 1) return true;
    }
    return false;
}

int main() {
    cin >> N;
    for( int i = 0; i < N; i++ ){
        cin >> arr[i];
    }

    // ペアを初期化
    for( int i = 0; i < N; i++ ){
        for( int j = 0; j < N; j++ ){
            p[i][j] = -1;
        }
    }
    for( int k = 0; k < N; k++ ){
        for( int i = 0; i < N; i++ ){
            for( int j = 0; j < N; j++ ){
                if( arr[k] == arr[i] + arr[j] ) p[k][i] = j;
            }
        }
    }

    // dpを更新
    fill( dp, dp + (1 << MAX_N), INF );
    dp[1] = 1; 
    for( int i = 0; i < N - 1; i++ ){
        for( int mask = 1 << i; mask < 1 << (i+1); mask++ ){
            if( dp[mask] == INF ) continue;

            // maskの変数を使って次の数字は作れるか?
            if( !canCreate( i+1, mask ) ) continue;
            
            // 変数を増やす場合
            int baseMask = mask | (1 << (i+1));
            dp[baseMask] = min( dp[baseMask], dp[mask] + 1 );

            // 変数を上書きする場合
            for( int j = 0; j <= i; j++ ){
                if( ((mask >> j) & 1) == 0 ) continue;
                int newMask = baseMask & ~(1 << j);
                dp[newMask] = min( dp[newMask], dp[mask] );
            }
        }
    }

    // 答えは最後の変数のbitが1となっている中の最小の値
    int res = INF;
    for( int mask = 1 << (N - 1); mask < 1 << N; mask++ ){
        res = min( res, dp[mask] );
    }
    if( res == INF ) res = -1;

    cout << res << endl;
}