AOJ1161 Verbal Arithmetic

問題概要
覆面算を解く.
なお以下の条件を満たしているものとする.

• 

• それぞれの文字はそれぞれ独立した数字を表す

• が2以上のとき, Leading zeroは不可

• 与えられる文字列数は3以上12以下, 文字列全体に含まれる文字の種類数は1以上10以下

解法
適当な全探索コードを書くとTLEした.
定数倍高速化したコードを投げたら8.2sで通ったが, 他の方のコードだとmsで通っているみたいなので別の方針を考える.

各文字について次のように分解する
例：

そして, 左辺から右辺を引くことで方程式を解く問題に帰着できる.
各変数は0から9の値を取ることや同じ値を持たないことに注意しながら半分全列挙をすることで高速に解くことができる.

ACコード

map<int, vector<ll>> han;
map<int, vector<ll>> han2;
bool lead[26];
void dfs(int d, int mask, int end, ll val, vector<pair<ll, char>>& v){
    if(d == end){
        han[mask].push_back(val);
        return;
    }

    int word = v[d].second - 'A';

    for(int i=0; i<10; i++){
        if((mask & (1<<i)) != 0) continue;
        if(i == 0 && lead[word]) continue;
        dfs(d+1, mask | (1<<i), end, val + v[d].first*i, v);
    }
}

void dfs2(int d, int mask, int end, ll val, vector<pair<ll, char>>& v){
    if(d == end){
        han2[mask].push_back(val);
        return;
    }
    int word = v[d].second - 'A';

    for(int i=0; i<10; i++){
        if((mask & (1<<i)) != 0) continue;
        if(i == 0 && lead[word]) continue;

        dfs2(d+1, mask | (1<<i), end, val + v[d].first*i, v);
    }
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(18);
    int N;
    while(cin >> N, N){
        han.clear();
        han2.clear();
        map<char, int> mp;
        for(int i=0; i<26; i++)lead[i] = false;
        for(int i=0; i<N-1; i++){
            string s; cin >> s;
            ll cur = 1;
            for(int j=s.size()-1; j>=0; j--){
                mp[s[j]] += cur;
                cur *= 10; 
            }
            if(s.size() != 1){
                lead[s[0]-'A'] = true;
            }

        }
        {
            string s; cin >> s;
            ll cur = 1;
            for(int j=s.size()-1; j>=0; j--){
                mp[s[j]] -= cur;
                cur *= 10;
            }
            if(s.size() != 1){
                lead[s[0]-'A'] = true;
            }
        }

        vector<pair<ll, char>> v;
        for(auto e: mp){
            v.push_back(make_pair(e.second, e.first));
        }

        int n = v.size()/2;
        int n2 = v.size()-n;

        dfs(0, 0, n, 0, v);

        dfs2(n, 0, v.size(), 0, v);
        int ans = 0;
        for(auto e: han){
            int mask = e.first;

            for(auto f: han2){
                int mask2 = f.first;
                if((mask & mask2) != 0) continue;
                
                for(int i=0;i<e.second.size(); i++){
                    for(int j=0;j<f.second.size(); j++){
                        if(e.second[i]+f.second[j] == 0) {
                            ans++;
                        }
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}