torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder, SRM 613, Division 2, Level 3 : TaroCards

問題概要

 2 つの正整数が書かれたカードが N 枚ある。i 番のカードに書かれた一つ目の値は first[ i ] であり、二つ目のそれは second[ i ] である。ここで、配列 first, second は、次の condition を満たす。

  • first はサイズ N の順列となっている。すなわち、[ 1, N ] の整数が丁度一度ずつ出現する
  • second の任意の要素 s は 1 \leq s \leq 10 を満たす

 さらに、整数 K ( 1 \leq K \leq 2N ) が与えられる。カードの部分集合であって、それに含まれるカードに書かれた相異なる整数の数が 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;
	}
};