はまやんはまやんはまやん

hamayanhamayan's blog

ox Concatenation [CPSCO2019 Session4 E]

https://atcoder.jp/contests/cpsco2019-s4/tasks/cpsco2019_s4_e

解説(部分点解法)

https://atcoder.jp/contests/cpsco2019-s4/submissions/5285574

以下に疑似満点解法もあるが、こちらも紹介。
 
まずは、自明なNoパターンを弾いておこう。
「ox,xo,o,xの個数から使えるo,xの個数」と「文字列Sに含まれるo,xの個数」が一致するかを見ておこう。
自明なNoパターンを見つけたら、そうそうに排除しておくことで、一部のコーナーケースを回避できたりする。
 
ここから本番だが、ox,xoを作るのは大変そうだが、o,xはどこに置いても大丈夫そうな感じがある。
つまり、文字列SにかぶらないようにoxをA個、xoをB個おければSを作れそうな感じがする。
これは直感的に正しく、実際にも正しい。
よって、「文字列SにかぶらないようにoxをA個、xoをB個おけるか」という問題に帰着した。
 
これば部分点解法の制約であればDPで解決できる。
dp[i][a] := i文字目まで確定していて、置くべきoxがまだa個あるときに、置くべきxoの個数の最小個数
dp[0][A] = Bで他はinfで埋めた状態でスタート。
あとは、oxで置くか、xoで置くか、何も置かずに文字を1つ進めるかの3つの遷移でDPを埋めていき、
dp[N][0]==0になっていれば、置けたことになる。

int N; string S; int A, B, C, D;
int dp[4040][4040];
//---------------------------------------------------------------------------------------------------
#define yes "Yes"
#define no "No"
string solve() {
int maru = 0, batsu = 0;
	fore(c, S) {
		if (c == 'o') maru++;
		else batsu++;
	}
 
	if (A + B + C != maru or A + B + D != batsu) return no;
 
	S += "#";
 
	rep(i, 0, N + 1) rep(a, 0, A + 1) dp[i][a] = inf;
	dp[0][A] = B;
	rep(i, 0, N) rep(a, 0, A + 1) if(dp[i][a] < inf) {
		chmin(dp[i + 1][a], dp[i][a]);
 
		if (S[i] == 'o' and S[i + 1] == 'x' and 0 < a) chmin(dp[i + 2][a - 1], dp[i][a]);
		if (S[i] == 'x' and S[i + 1] == 'o' and 0 < dp[i][a]) chmin(dp[i + 2][a], dp[i][a] - 1);
	}
 
	if (dp[N][0] == 0) return yes;
	return no;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> S >> A >> B >> C >> D;
	cout << solve() << endl;
}

解法(満点解法)

公式解説のつなぎ、hamayanhamayanのポエムとして見てほしい。
自分も解法わかってないし。

  • DP解は思いついたけど、これの高速化は思いつかない
  • 今回の問題若干マッチング問題っぽくないか?
  • マッチング問題って貪欲解あるケース結構あるよね これ
  • 全体見てみると、xoxoxoとかoxoxoとかの塊毎に独立して、数えることができそう
  • これ貪欲やな。無理です。

コンテスト後TLにて

  • oxoxoとxoxoxの価値がoxに取ってもxoに取っても一緒(beetさん)
  • oxoxox...oxのうちフルに使えるものの個数で全探索。短い方から使っていく(kobaさん)
  • oxかxoどちらかに全力を注いでもいいことがわかって、どっちも試す(latteさん)
  • ooとかxxの部分で切って、頑張る(beetさん)
  • S を oxoxo xoxo o xo とSi=Sjのところで分解して貪欲(drafearさん)