hogecoder

tsutaj 競技プログラミングの記録

TopCoder SRM 716 Div1 Easy: ConstructLCS

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

以下の条件を全て満たすような '0' と '1' のみからなる文字列  A, B, C を構成せよ。

解説

 ab \gt bc \gt ca を仮定すると、次のような文字列を構成すれば良いことが分かります。

  • 文字列  A ab 文字の '0'
  • 文字列  B ab 文字の '0' と、  bc 文字の '1'
  • 文字列  C bc 文字の '1' と、  ca 文字の '0'

なぜ大小関係が必要かというと、これがないと色々と不都合が生じる可能性があるからです ( B C の LCS について、  bc のほうではなく  \min(ab, ca) の方が採用されるかも、などなど)

しかし実際にはこの仮定はないため、どうするかと言うと、上と同じ方法で文字列を  3 つ作り、そのうちどれを  A に、どれを  B に、どれを  C に当てはめるかを全て試し、その都度 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 "";
    }
};