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; }