2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest,D: Packmen Strike Back

http://codeforces.com/problemset/problem/883/D

これは考察系のDP。

場合分けでtrivialな場合は別で処理します。

非自明(Pが2つ以上ある)の時、まず二分探索して、距離Kすすめるとき*をすべて覆えるか?という問題を解くことを考えます。

dp(i):=i番目のPを使った時、*をカバーできる範囲が[0, l)だとして、lの最大値とします。
するとi+1番目のPがi番目の時点でカバーできているのなら、区間は必ず右に伸ばせばいいです。
カバーできてないとすると、[dp(i),P(i+1)の区間をカバーするのはi+１番目のP、またはi+2番目のPとなります。
なぜなら、i+k番目(k>=3)のPでその区間をカバーしたとすると、i+k-1番目のPは右に伸ばす場合が、dp(i+k)の候補になりえます。しかしi+k-2以下は右に伸ばすのも左に伸ばすのも自由になり、i+1番目のPでカバーしても問題ありません。

なのでdp(i)を更新するためにはdp(i-1)とdp(i-2)の値のみだけが必要で、dp(N)で求められます。
全部でO(NlogN)となり十分間に合います。

O(N)個参照しないといけないと見せて実はO(1)で済む系DPですね。
http://codeforces.com/contest/853/problem/D（解いてないけど)
とかもこれと同じ系統です。

int N, M;
string str;
int minv, maxv;
int P[1000010];
int S[1000010];
int dp[1000010];

bool exist(int l, int r) {
	return ((r > l) && (S[r] - S[l]));
}

bool C(int m) {
	rep(i, 0, M + 1) dp[i] = 0;
	rep(i, 1, M + 1) {
		int e = P[i - 1] + 1;
		if(!exist(dp[i - 1], e - m - 1)) MAX(dp[i], e);
		if(!exist(dp[i - 1], e)) MAX(dp[i], e + m);
		if(i != 1) {
			int f = P[i - 2] + 1;
			if(!exist(dp[i - 2], e - m - 1)) MAX(dp[i], f + m);
		}
	}
	// debug(m, vi(dp, dp + M + 1));
	return dp[M] > maxv;
}

void solve() {
	cin >> N >> str;
	M = 0;
	rep(i, 0, N) {
		if(str[i] == 'P') P[M++] = i;
		S[i + 1] = S[i] + (str[i] == '*');
	}
	minv = inf; maxv = -inf;
	rep(i, 0, N) {
		if(str[i] != '*') continue;
		MIN(minv, i);
		MAX(maxv, i);
	}
	if(M == 1) {
		int p = P[0];
		int lc = S[p], rc = S[N] - S[p];
		if(lc > rc) {
			cout << lc << " " << p - minv << "\n";
		}
		else if(lc < rc) {
			cout << rc << " " << maxv - p << "\n";
		}
		else { //lc == rc
			cout << lc << " " << min(maxv - p, p - minv) << "\n";
		}
		return;
	}
	C(2);
	int lv = 0, rv = N;
	while(rv - lv > 1) { //minimize
		int m = (lv + rv) / 2;
		if(C(m)) rv = m;
		else lv = m;
	}
	cout << S[N] << " " << rv << "\n";
}