AtCoder Beginner Contest 183, E : Queen on Grid

問題文

　https://atcoder.jp/contests/abc183/tasks/abc183_e

問題概要

　高さ $H$ ，幅 $W$ のグリッド状の盤面を考える．セル $( i, j )$ は空白か壁かのいずれかである．
　この盤面の位置 $( 1, 1 )$ に駒が置かれている．駒は，右，右下，下のいずれかの方向に，壁にぶつからない限りにおいて何マスでも移動できる（移動方向が制限された，チェスのクイーン）．この駒を $( 1, 1 )$ から $( H, W )$ へ移動させる方法の総数はいくらか？

制約

• $1 \leq H, W \leq 2{,}000$

解法

　ある程度 DP に慣れている人なら，まず最初にやりたくなるのは，

• $dp_{ i, j } := \text{ 位置 $( i, j )$ に到達する方法の総数}$

という DP かと思いますが，遷移の総数が $O( H + W )$ 個あるため，状態数と併せて考えると TLE してしまいます．なのでこれよりも計算量を落としてあげる必要がありますが，状態のとり方で，位置に関する添字は落とせる気がしないので，遷移の方を減らす方向性で考えます．具体的には，ある方向へ移動するとき，移動距離を全て試すというループを回すことなく，同様の移動を扱う方法を考えます．
　そこで，次のように状態をとることを考えます．

• $dp_{ i, j, k } := \text{ 位置 $( i, j )$ に到達していて，駒の状態が $k$ }$

$k$ の詳細は，

• $k = 0$ → 駒を置いている状態
• $k = 1$ → 駒を持ち上げていて，移動方向は右
• $k = 2$ → 駒を持ち上げていて，移動方向は右下
• $k = 3$ → 駒を持ち上げていて，移動方向は下

です．DP の更新では各 $i, j$ で $dp_{ i, j, k }$ ($k > 0)$ から $dp_{ i, j, 0 }$ への足し込み（持ち上げている駒を一旦置くパターン）と，新たに移動を始めるパターンと，持ち上げた駒をそのままその先へ移動させるパターンをそれぞれ試します*1．
　これで，計算量としては $O( HW )$ 時間に落ち，間に合わせることができます．

コード

constexpr int MOD = 1'000'000'007;

constexpr int dy[] = { 0, 0, 1, 1 };
constexpr int dx[] = { 0, 1, 1, 0 };

int main()
{
	cin.tie( nullptr );
	ios::sync_with_stdio( false );
	cout << setprecision( 12 ) << fixed;

	IN( int, H, W );
	VS board( H );
	cin >> board;

	const auto empty = [&]( const int y, const int x )
	{
		return y < H && x < W && board[y][x] == '.';
	};

	static int dp[ 2048 ][ 2048 ][4];
	// dp[ y coordinate ][ x coordinate ][ direction ] := ways
	dp[0][0][0] = 1;
	REP( i, H )
	{
		REP( j, W )
		{
			REP( k, 1, 4 )
			{
				( dp[i][j][0] += dp[i][j][k] ) %= MOD;
			}

			REP( d, 1, 4 )
			{
				const int ny = i + dy[d];
				const int nx = j + dx[d];
				if ( !empty( ny, nx ) )
				{
					continue;
				}
				( dp[ ny ][ nx ][d] += dp[i][j][0] ) %= MOD;
				( dp[ ny ][ nx ][d] += dp[i][j][d] ) %= MOD;
			}
		}
	}

	cout << dp[ H - 1 ][ W - 1 ][0] << endl;

	return 0;
}

*1:添字の説明が面倒になってしまったのでコード参照＞＜；