問題概要
2 つの正整数が書かれたカードが N 枚ある。i 番のカードに書かれた一つ目の値は first[ i ] であり、二つ目のそれは second[ i ] である。ここで、配列 first, second は、次の condition を満たす。
- first はサイズ N の順列となっている。すなわち、[ 1, N ] の整数が丁度一度ずつ出現する
- second の任意の要素 s は
を満たす
さらに、整数 K ( ) が与えられる。カードの部分集合であって、それに含まれるカードに書かれた相異なる整数の数が K を超えないものの数を求めよ。
解法
各カードについて選ぶか選ばないかを選択することが可能なので、可能な状態の数は指数オーダーとなってしまいます。従って、同一視できる状態をまとめて計算する必要があります。
ここで、first, second に関する意味深な制約に着目すると次のことが言えます。
- 10 より大きい値は、全体でも一つずつしか無い
- 10 以下の値は複数出現しうるが、10 以下の整数の集合は 2^10 = 1024 通りしかない
この二点を踏まえると、カードを先頭（番号の若いもの）から順番に使うか使わないかを試していく次のような DP を考えることができます。
- dp[ i 枚考慮した ][ j 種類の値をもっている ][ s := 10 以下の値の集合の整数表現 ] := 総数
基底状態は dp[ 0 ][ 0 ][ 0 ] = 1 で、それ以外の状態の初期値は 0 としておきます。
dp[ i ][ j ][ s ] から、次のカードを使うような遷移を考えるとき、j, s の変化分を計算する必要がありますが、これは s の変化分を先に計算すると楽に計算できます。小さい値の集合表現をビットでもつので、簡単のために first, second の値を予め全てデクリメントしておきます。まず、新しい s の値である ns は、s が表す集合に first[ i ] と second[ i ] を加えるので、s | ( 1LL << first[ i ] ) | ( 1LL << second[ i ] ) の 2^10 = 1024 による剰余となります。このとき、持っている 9 以下（本来の 10 以下）の値の数の増分は、s から ns になって増えたビットの数に等しいので、popcount( s ^ ns ) です。10 以上の値（本来の 10 を超える値）の種類が増えるかどうかは、10 <= first[ i ] と同値です。従って、新しい j の値である nj は j + popcount( s ^ ns ) + ( 10 <= first[ i ] ) と計算されます。まとめると、dp[ i ][ j ][ s ] からの遷移は次のようになります。
- dp[ i + 1 ][ j ][ s ] を更新（ i 番目のカードを使わない場合）
- dp[ i + 1 ][ nj ][ ns ] を更新 ( i 番目のカードを使う場合）
- ただし、ns = ( s | ( 1LL << first[ i ] ) | ( 1LL << second[ i ] ) ) % ( 1 << 10 ), nj = popcount( s ^ ns ) + ( 10 <= first[ i ] )
全ての状態の値を計算したあと、有効な j, s について Σ( dp[ N ][ j ][ s ] ) を計算することで、答えが求まります。
コード
using LL = long long; template < typename T > using VT = vector<T>; template < typename T > using VVT = vector< VT<T> >; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define FOR( e, c ) for ( auto &e : c ) #define ALL( c ) (c).begin(), (c).end() class TaroCards { public: long long getNumber( vector <int> first, vector <int> second, int K ) { const int N = first.size(); { auto f = bind( minus<int>(), placeholders::_1, 1 ); transform( ALL( first ), first.begin(), f ); transform( ALL( second ), second.begin(), f ); } VT< VVT<LL> > dp( N + 1, VVT<LL>( K + 1, VT<LL>( 1 << 10 ) ) ); dp[0][0][0] = 1; REP( i, 0, N ) { REP( j, 0, K + 1 ) { REP( s, 0, 1 << 10 ) { const int ns = ( (LL)s | ( 1LL << first[i] ) | ( 1LL << second[i] ) ) % ( 1 << 10 ); const int nj = j + __builtin_popcount( s ^ ns ) + ( 10 <= first[i] ); if ( nj <= K ) // use { dp[ i + 1 ][ nj ][ ns ] += dp[i][j][s]; } { // not use dp[ i + 1 ][j][s] += dp[i][j][s]; } } } } LL res = 0; FOR( v, dp.back() ) { res += accumulate( ALL( v ), 0LL ); } return res; } };
