TopCoder SRM 576, Division 1, Level 2 : TheExperiment

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12509&rd=15496

概要

N 個の蛇口が等間隔に並んでおり、その下に M 枚のスポンジを重ねて並べる。
一番上にあるスポンジは、その真上にある蛇口から落ちてくる水滴を吸収する。
それぞれの蛇口から落ちる水滴の数と、スポンジの数 M 、スポンジの幅 L 、整数 A, B が与えられる。
それぞれのスポンジが吸収する水滴の数が A 以上 B 以下になるようなスポンジの置き方の総数を求めよ。

解法

一番上にあるスポンジだけを考えると、重複しないちょうど M 個（ A の制約のため）の区間で表すことができます。

ではまず、隙間を空けずに接している区間郡について考えます。
この場合、一番上になるスポンジが一個以上存在するため、少なくとも一つの幅 L の区間が含まれる状態が、valid な状態であると言えます。
全体では、いくつかの valid な区間郡を並べる方法の総数を求めることになります。

並べ方の総数を求めるには、
dp[ 位置 ][ 使ったスポンジの枚数 ][ 状態 ]
として動的計画法をします。

三番目のパラメータである「状態」について説明します。
各場所について、その状態は以下の三通りあります。

• 0 := 左側が区間郡に接していない
• 1 := 左側が区間郡に接していて、その区間郡は幅 L の区間を含まない
• 2 := 左側が区間郡に接していて、その区間郡は幅 L の区間を含む

状態の遷移については以下のようになります

• 区間を置く
  • 前の状態が 2 であるか、置く区間の幅が L なら次の状態は 2
  • それ以外の場合は次の状態は 1
• 1 以外の状態から、空白を開ける
  • 次の状態は 0

コード

typedef long long LL;
typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

const int MOD = 1000000009;

typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

class TheExperiment
{
public:
	int countPlacements( vector <string> intensity, int M, int L, int A, int B )
	{
		const string S( accumulate( ALL( intensity ), string() ) );
		const int N = S.size();

		VI csum( 1, 0 );
		{
			VI ary( N );
			REP( i, 0, N )
			{
				ary[i] = S[i] - '0';
			}
			partial_sum( ALL( ary ), back_inserter( csum ) );
		}

		vector< VVLL > dp( N + 1, VVLL( M + 1, VLL( 3, 0 ) ) );
		dp[0][0][0] = 1;

		REP( i, 0, N )
		{
			REP( j, 0, M )
			{
				REP( k, 0, 3 )
				{
					dp[i][j][k] %= MOD;

					for ( int l = 1; l <= L && i + l <= N; l++ )
					{
						int drops = csum[ i + l ] - csum[i];
						if ( !( A <= drops && drops <= B ) )
						{
							continue;
						}

						int nextK = k == 2 || l == L ? 2 : 1;
						dp[ i + l ][ j + 1 ][ nextK ] += dp[i][j][k];
					}
				}
			}

			REP( j, 0, M + 1 )
			{
				REP( k, 0, 3 )
				{
					if ( k == 1 )
					{
						continue;
					}
					dp[ i + 1 ][j][0] += dp[i][j][k];
				}
			}
		}

		return ( dp[N][M][0] + dp[N][M][2] ) % MOD;
	}
};