これは同時開催のオープンなかったのね。解説も未だになし…?
http://code-festival-2015-morning-middle.contest.atcoder.jp/tasks/cf_2015_morning_easy_d
問題
文字列Sが与えられる。
幾つかの文字を削除し、Sを同じ単語を2回繰り返した形にしたい。
最小何文字削除すればよいか。
解法
Sを前と後ろに二分割する。
分割位置を総当たりし、前と後ろのLCSを取ろう。
最長のLCSが分かれば、それ以外の文字を消せばよいだけ。
int L; string S; // 前から検索 int dpdp[111][111]; int lcs(string& AA,string& BB) { int x,y,ma=0; ZERO(dpdp); FOR(x,AA.size()) FOR(y,BB.size()) { if(AA[x]==BB[y]) dpdp[x+1][y+1]=max(dpdp[x+1][y+1],dpdp[x][y]+1); dpdp[x+1][y+1]=max(dpdp[x+1][y+1],dpdp[x][y+1]); dpdp[x+1][y+1]=max(dpdp[x+1][y+1],dpdp[x+1][y]); ma=max(ma,dpdp[x+1][y+1]); } return ma; } void solve() { int i,j,k,l,r,x,y; string s; cin>>L>>S; int mi=L; for(x=1;x<=L-1;x++) { string a=S.substr(0,x), b=S.substr(x); mi=min(mi, L-2*lcs(a,b)); } cout<<mi<<endl; }
まとめ
計算量間に合うか心配だったけど、O(|S|^3)だから余裕か。