TopCoder SRM 590, Division 2, Level 3 : FoxAndShogi

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12745&rd=15702

概要

'.', 'U', 'D' からなるグリッド状の盤面が与えられる。
一回の操作は次の二つの操作の内いずれかを行うことができる。

• その上のセルが '.' である 'U' を一つ選び、上のセルと入れ替える
• その下のセルが '.' である 'D' を一つ選び、下のセルと入れ替える

任意回の操作が可能であるとき、作れる盤面は何通りあるか MOD で求めよ。

解法

駒は上下にしか動かないので、列毎に独立になります。
従って、列毎に結果を計算して積をとったものが答えです。

一つの列について、作れる盤面が何通りあるか求める方法について考えます。
「駒を動かす」と考えると状態遷移が多すぎて計算できないので、「駒を配置し直す」と考えます。
こう考えたとき、'U' の駒を置ける範囲は元あった場所より上の範囲で、'D' の駒を置ける範囲は元あった場所より下の範囲です。
列を上から舐めたときに出現する順番通りに駒を再配置していくと考えると、駒の順番が入れ替わらないようにする必要があります。
これは、常に直前に置いた駒よりも下に置くようにすればよいので、次のような DP を考えることができます。
　dp[ i 個の駒を配置した ][ 使える範囲は j セル目以下 ] := 場合の数
計算が終わったあと、dp[ M ][ j ] （ただし M は列中の駒の数）の和が答えになります。
次の駒を置ける範囲は、着目している駒が元あった場所を p とすると

• 'U' のとき、上端は j 、下端は p
• 'D' のとき、上端は max( j, p ) 、下端は N - 1

上端 ＞ 下端　である場合は次の駒を置くことができません。

以下のコードでは、列毎に処理をするときに（わたしの脳内で）イメージが横向きになるので、'U' -> 'L', 'D' -> 'R' と変換しています。

コード

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

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

const int MOD = 1000000007;

class FoxAndShogi
{
public:
	int N;

	int differentOutcomes( vector <string> board )
	{
		this -> N = board.size();

		LL res = 1;

		REP( ix, 0, N )
		{
			( res *= solveLn( [&](){
				string res;
				REP( i, 0, N )
				{
					const int ch = board[i][ ix ];
					res += ch == '.' ? ch : ch == 'U' ? 'L' : 'R';
				}
				return res;
				}() ) ) %= MOD;
		}

		return res;
	}

	LL solveLn( const string &line )
	{
		string cs;
		VI ps;
		REP( i, 0, N )
		{
			if ( line[i] == '.' )
			{
				continue;
			}
			cs += line[i];
			ps.PB( i );
		}

		const int M = cs.size();

		VVI dp( M + 1, VI( N + 1, 0 ) );
		dp[0][0] = 1;

		REP( i, 0, M )
		{
			REP( j, 0, N )
			{
				int left = j, right = N - 1;
				if ( cs[i] == 'L' )
				{
					right = ps[i];
				}
				else
				{
					left = max( left, ps[i] );
				}

				REP( k, left, right + 1 )
				{
					( dp[ i + 1 ][ k + 1 ] += dp[i][j] ) %= MOD;
				}
			}
		}

		return accumulate( ALL( dp.back() ), 0LL );
	}
}