SRM528 Div1 Medium - SPartition
問題
長さn(:偶数)で 'o' と 'x' のみからなる文字列sが与えられ、これの各文字を赤か青で塗る
赤で塗った文字列と青で塗った文字列が同じになるような塗り方が何通りあるか求めよ
2 <= n <= 40
解法
半分全列挙
前半の赤い部分をx、青い部分をyとする
まずxとyの最長共通接頭辞(LCP)の長さはx,yのうち短い方の長さに一致している必要がある
x,yのうち長さがより長い方の色をza、そっちの色で塗られた文字列のうちLCPに含まれない部分の文字列をsaとする
次に後半の赤い部分をx、青い部分をyとする
こっちも同様にxとyの最長共通接尾辞(LCS)の長さがx,yのうち短い方の長さに一致している必要がある
x,yのうち長さがより長い方の色をzb、そっちの色で塗られた文字列のうちLCSに含まれない部分の文字列をsbとする
すると、前半でza≠zbかつsa=sbであるような塗り方をしたものの後ろにこの塗り方をしたものをくっつけたものは条件を満たす
こういうペアを数え上げれば良い
↓こういう感じ
creep06.hatenablog.com
これにめっちゃ似てるな
今回の問題の方が若干考えることが多い
実装
mapで数え上げる
xとyが全く同じ文字列である場合は別に扱う必要がある
そういう場合は0、yの方が長い場合は1、xの方が長い場合は2と番号付けした
class SPartition { public: ll getCount(string s) { ll n = s.size()/2, res = 0; map<pair<int, string>, ll> p; rep(i,1<<n) { string x, y; rep(j,n) (i>>j&1 ? x : y).push_back(s[j]); int l = min(x.size(), y.size()), ok = 1; rep(j,l) if (x[j]!=y[j]) ok = 0; if (!ok) continue; if (x.size()==y.size()) p[{0, ""}]++; else if (x.size()==l) p[{1, y.substr(l)}]++; else p[{2, x.substr(l)}]++; } rep(i,1<<n) { string x, y; rep(j,n) (i>>j&1 ? x : y).push_back(s[n+j]); int l = min(x.size(), y.size()), ok = 1; rep(j,l) if (x[x.size()-j-1]!=y[y.size()-j-1]) ok = 0; if (!ok) continue; if (x.size()==y.size()) res += p[{0, ""}]; else if (x.size()==l) res += p[{2, y.substr(0, y.size()-l)}]; else res += p[{1, x.substr(0, x.size()-l)}]; } return res; } };
AGCの問題を連想してこういう解き方をしたけど、このコードは文字が何種類あっても解ける
つまり文字列が 'o' か 'x' の2文字のみからなるって制約を使ってない
これを利用した別の解き方がありそう?