IOI 2008 Day2 - Linear Garden

解法 :

L がある場所ではその位置まででもっとも早いバランスのある文字列となる.
P がある場所は, そこをL に置き換えたときに何通りのバランスのある庭園が出きるかを解に加算すれば良く, これは数え上げdp でできる.

dp の状態としては[いまの位置][どこまで下がったか][どこまで上がったか][今の高低差はどれくらいか] 持てば十分である... がバグりました. (85 / 100 点) (だれかバグとってください><)

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int N, M;
static char s[1000001];
 
int main()
{
	scanf("%d\n%d", &N, &M);
	scanf("%s", s);
	
	
	int dx = 2, mindx = 0, maxdx = 4;
	
	vector<pair<pair<int, int>, pair<int, int> > > check;
	
	for (int i = 0; i < N; i++){
		if (s[i] == 'L'){
			dx++;
			if (dx > 2) mindx = max(mindx, dx - 2);
		}
		else {
			int mi = mindx;
			if (dx > 1) mi = max(mi, dx - 1);
			if (mi <= dx + 1 && dx + 1 <= maxdx)
				check.push_back(make_pair(make_pair(i, dx + 1), make_pair(mi, maxdx)));
			dx--;
			if (dx < 2) maxdx = min(maxdx, dx + 2);
		}
	}
	reverse(check.begin(), check.end());
	
	int dp[2][5][5][5]; //今の場所, min(高低差), max(高低差), now(高低差)	
 
	memset(dp, 0, sizeof(dp));
	dp[0][2][2][2] = 1;
	
	int pos = 0, idx = 0;
	
	for (int i = 1; i <= N; i++){
		memset(dp[i & 1], 0, sizeof(dp[i & 1]));
		for (int j = 0; j < 5; j++){
			for (int k = j; k <= min(4, j + 2); k++){
				for (int l = 0; l < 5; l++){
					if (k - (l - 1) <= 2 && l) {
						dp[i & 1][min(j, l - 1)][k][l - 1] += dp[(i - 1) & 1][j][k][l];
						dp[i & 1][min(j, l - 1)][k][l - 1] %= M;
					}
					if (l + 1 - j <= 2 && l < 4){
						dp[i & 1][j][max(k, l + 1)][l + 1] += dp[(i - 1) & 1][j][k][l];
						dp[i & 1][j][max(k, l + 1)][l + 1] %= M;
					}
				}
			}
		}
		
		if (idx != check.size() && N - check[idx].first.first == i){
			for (int j = check[idx].second.first; j <= check[idx].second.second; j++){
				for (int k = j; k <= min(j + 2, check[idx].second.second); k++){
					for (int l = j; l <= k; l++){
						pos += dp[1 - i & 1][j][k][l];
						pos %= M;
					}
				}
			}
			idx++;
		}
	}
	
	printf("%d\n", (pos + 1) % M);
	
	return (0);
}

DP できない人になってしまったので, 数え上げ的なアプローチを試みます.
P が出てくる前までの上限と下限を$hi$, $lo$ とします. 現在の高低差を$dx$ とすると, そこをP からL に置き換えることで高低差が$dx + 2$ になることに注意します.

1. $\max (dx + 2, hi) - lo > 2$ のとき
P をL に置き換えることでバランスのとれない残念な庭園になったので, この場合に新たに生じる庭園は$0$ 個です.

2. $\max (dx + 2, hi) - lo = 2$ のとき
動ける範囲が決まっているので, 残りの花の個数を$K$ としたときにどれだけ庭園が生じるかを考えます.
・$dx + 2$ が$lo + 1$ と等しいとき
　このとき, 1 個目にはL とP のどちらを置いても良いですが, 2 個目は前回の結果に依存した花になってしまいます. 同様に, 奇数文字目を自由に決められるので, $2^{[\frac{K + 1}{2}]}$ 個の庭園ができることが分かります.
・そうでないとき
　このときは上と同じような議論から$2^{[\frac{K}{2}]}$ 個の庭園が出きることが分かります.

3. $\max (dx + 2, hi) - lo = 1$ のとき
まだ動いた範囲に1 つ余裕があるので, 2 段の間を媒介出きることが分かります. 媒介できる2 段は2 通りあって, それぞれ2. の場合分けの一方の庭園が生じますが, LPLPLP... の形の庭園を重複して数えてしまうので, $2^{[\frac{K}{2}]} + 2^{[\frac{K + 1}{2}]} - 1$ 個の庭園が生じることが分かります.

4. $\max (dx + 2, hi) - lo < 1$ のとき
そんな場合あるわけないだろ！いい加減にしろ！

...ということで, 実直に場合分けして$O(N)$ 時間で個数を算出できます. タイトルと同じようにlinear に答えがでていいですね...

コード (100 / 100 点):

#include <cstdio>
#include <algorithm>

using namespace std;

char gar[1000001];
int pow2[1000001];

int main()
{
	int N, M;
	
	scanf("%d %d", &N, &M);
	scanf("%s", gar);
	
	pow2[0] = 1;
	for (int i = 1; i <= N; i++) pow2[i] = (2 * pow2[i - 1]) % M;
	
	int ans = 0, K = N;
	int nowdx = 0, mindx = 0, maxdx = 0;
	for (int i = 0; gar[i]; i++){
		K--;
		if (gar[i] == 'P'){
			int ndx = nowdx + 1;
			if (max(ndx, maxdx) - mindx == 1) ans = (ans + pow2[K / 2] + pow2[(K + 1) / 2] + M - 1) % M;
			else if (max(ndx, maxdx) - mindx == 2) ans = (ans + pow2[(K + (mindx + 1 == ndx)) / 2]) % M;
			nowdx--;
			mindx = min(mindx, nowdx);
		}
		else {
			nowdx++;
			maxdx = max(maxdx, nowdx);
		}
	}
	
	printf("%d\n", (ans + 1) % M);
	
	return (0);
}

DP 出来るようになりたいです...

Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

IOI 2008 Day2 - Linear Garden