torus711 のアレ

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

Codeforces #271, D : Flowers

問題概要

 'W', 'R' からなる文字列であって、出現する全ての 'W' を互いに交差しない、連続した長さ k の区間に分割できるものについて考える。
 以下の形式のクエリを t 件処理せよ。

  • 二つの整数 a, b ( a \leq b \leq 10^5 ) が与えられる。長さが a 以上 b 以下であり、上記の性質を満たす文字列の総数を MOD で求めよ。

 t \leq 10^5

解法

 クエリの個数がそれなりに多いので、かなり高速に処理しなければなりません。同じクエリに対する答えは常に不変であるので、クエリの答えを全て前計算できれば、各クエリを定数時間で処理することができます。このとき、[ a, b ] の答えは [ 0, b ] の答えから [ 0, a ) の答えを引くことで求められることに注意すると、次のような動的計画法+累積和により答えを前計算できます。

  • dp[ i 文字並べた ] := 総数

文字列の末尾に文字を付け加えていくと考えると dp[ i ] からの遷移は 2 通りで、

  • 'R' を付け足す : dp[ i + 1 ] を更新
  • 'W' を付け足す : dp[ i + k ] を更新

となります。この計算が終わった後、DP テーブルの累積和を取れば、各 i に関して [ 0, i ] の答えが求まります。
 あとは、各クエリに対し適当に差分を求めて出力すれば、Time Limit 以内で問題を解くことができます。

コード

using VI = vector<int>; using VVI = vector<VI>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

constexpr int MAX_B = 100000;
constexpr int MOD = 1000000007;

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int t, k;
	cin >> t >> k;

	VI dp( MAX_B + 1 );
	dp[0] = 1;

	REP( i, 0, MAX_B )
	{
		( dp[ i + 1 ] += dp[i] ) %= MOD;
		if ( i + k <= MAX_B )
		{
			( dp[ i + k ] += dp[i] ) %= MOD;
		}
	}

	VI csum( 1, 0 );
	partial_sum( dp.begin() + 1, dp.end(), back_inserter( csum ), []( const int s, const int a ){ return ( s + a ) % MOD; } );

	REP( i, 0, t )
	{
		int a, b;
		cin >> a >> b;
		cout << ( csum[b] - csum[ a - 1 ] + MOD ) % MOD << endl;
	}

	return 0;
}