するめうめ
問題概要
原文 → TopCoder Statistics - Problem Statement
以下の条件を全て満たすような '0' と '1' のみからなる文字列 を構成せよ。
- と の最長共通部分列 (LCS) が
- と の LCS が
- と の LCS が
解説
を仮定すると、次のような文字列を構成すれば良いことが分かります。
- 文字列 → 文字の '0'
- 文字列 → 文字の '0' と、 文字の '1'
- 文字列 → 文字の '1' と、 文字の '0'
なぜ大小関係が必要かというと、これがないと色々と不都合が生じる可能性があるからです ( と の LCS について、 のほうではなく の方が採用されるかも、などなど)
しかし実際にはこの仮定はないため、どうするかと言うと、上と同じ方法で文字列を つ作り、そのうちどれを に、どれを に、どれを に当てはめるかを全て試し、その都度 LCS を取ります。どれかは必ず条件を満たしているので、これで解くことが出来ます。
ソースコード
class ConstructLCS { public: int calclcs(string a, string b) { int dp[1010][1010] = {}; int n = a.length(), m = b.length(); rep(i,0,n) rep(j,0,m) { if(a[i] == b[j]) dp[i+1][j+1] = dp[i][j] + 1; else dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]); } return dp[n][m]; } string construct(int ab, int bc, int ca) { vector<int> ns = {ab, bc, ca}; sort(ns.begin(), ns.end(), greater<int>()); vector<string> strs(3); strs[0] = string(ns[0], '1'); strs[1] = string(ns[0], '1') + string(ns[1], '0'); strs[2] = string(ns[1], '0') + string(ns[2], '1'); vector<int> perm = {0, 1, 2}; do { string ra = strs[perm[0]], rb = strs[perm[1]], rc = strs[perm[2]]; int nab = calclcs(ra, rb); int nbc = calclcs(rb, rc); int nca = calclcs(rc, ra); if(nab == ab && nbc == bc && nca == ca) { return ra + " " + rb + " " + rc; } }while(next_permutation(perm.begin(), perm.end())); return ""; } };