TopCoder SRM 694 DIV1 Medium - DistinguishableSetDiv1

難しく考えすぎてしまった。
文字列問題をみてもひるまずに解けるようになりたい。

問題概要

m 文字からなる文字列が n 個与えられる。
{0, 1, 2, …, m-1} の部分集合 bit のうち、
どの 2 つの文字列を選んでも、それらの文字列の bit に対応する部分文字列
(文字列 “string” に対して、bit = {0, 2, 3} に対応する文字列は “sri”)
が互いに等しくならないような部分集合 bit の個数を求めよ。

(制約)
・0 <= m <= 20
・0 <= n <= 1000

解法

部分集合 bit が条件を満たさない
⇔ ある 2 つの文字列 s, t が存在して、s[bit] = t[bit] である。
⇔ ある 2 つの文字列 s, t が存在して、bit は、s と t の極大共通部分文字列の部分文字列である。

そこで、nC2 通りの文字列の組み合わせそれぞれについて、
極大共通部分文字列を求めておいて(同じ文字の index を列挙するのみ)、
それらの部分集合がすべて列挙できればよい。

これは、以下のような dp で実現できる。計算量は、O(mn^2 + m2^m)。

dp[ S ] := 部分集合 S が条件を満たさないとき 1、満たすとき 0
として、

dp[S - {i}] |= dp[S]

コード

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

bool dp[(1<<21)];

class DistinguishableSetDiv1 {
public:
    int count(vector <string> answer) {
        int n = answer.size();
        int m = answer[0].size();
        int res = 0;
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n; ++i) for (int j = i+1; j < n; ++j) {
            int bit = 0;
            for (int k = 0; k < m; ++k) {
                if (answer[i][k] == answer[j][k])
                    bit += (1 << k);
            }
            dp[bit] = true;
        }
        for (int bit = (1 << m) - 1; bit >= 0; --bit) {
            if (dp[bit]) {
                for (int t = bit; t; t &= t-1) {
                    int sub = bit ^ (t & -t);
                    dp[sub] = true;
                }
            }
            else ++res;
        }
        return res;
    }
};