AOJ 1371 Infallibly Crack Perplexing Cryptarithm

解法

現れうる文字は高々8種類しかない.
なので各文字に対して何を割り当てるか全探索して構文解析するだけ.

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ret_type = double;
constexpr ret_type eps = 1e-8;

ret_type expr(string const& s, int& p);
ret_type term(string const& s, int& p);
ret_type factor(string const& s, int& p);
ret_type number(string const& s, int& p);

ret_type expr(string const& s, int& p) {
    ret_type val = term(s, p);
    while(p < (int)s.size() && (s[p] == '+' || s[p] == '-')) {
        if(s[p] == '-') {
            val -= term(s, ++p);
        } else {
            val += term(s, ++p);
        }
    }
    return val;
}

ret_type term(string const& s, int& p) {
    ret_type val = factor(s, p);
    while(p < (int)s.size() && s[p] == '*') {
        val *= factor(s, ++p);
    }
    return val;
}

ret_type factor(string const& s, int& p) {
    if(s[p] == '-') {
        return -factor(s, ++p);
    } else if(s[p] == '(') {
        ret_type res = expr(s, ++p);
        if(p >= (int)s.size() || s[p] != ')') throw std::logic_error("");
        ++p;
        return res;
    } else if(isdigit(s[p])) {
        return number(s, p);
    } else {
        throw std::logic_error("");
    }
}

ret_type number(string const& s, int& p) {
    if(s[p] != '0' && s[p] != '1') throw std::logic_error("");
    if(p + 1 < (int)s.size() && s[p] == '0' && isdigit(s[p + 1])) throw std::logic_error("");

    ret_type res = 0;
    while(p < (int)s.size() && isdigit(s[p])) {
        res *= 2;
        res += (s[p++] == '1');
    }
    return res;
}

int main() {
    string s;
    cin >> s;
    const int n = s.size();
    vector<char> cs;
    for(auto c : s) {
        if(isalpha(c)) {
            cs.push_back(c);
        }
    }
    sort(begin(cs), end(cs));
    cs.erase(unique(begin(cs), end(cs)), end(cs));

    vector<char> v = {'0', '1', '+', '-', '*', '=', '(', ')'};
    sort(begin(v), end(v));

    if(cs.size() > v.size()) {
        cout << 0 << endl;
        return 0;
    }

    int ans = 0;
    set<string> checked;
    do {
        string t;
        for(auto c : s) {
            if(isalpha(c)) {
                t += v[find(begin(cs), end(cs), c) - begin(cs)];
            } else {
                t += c;
            }
        }
        if(count(begin(t), end(t), '=') != 1) continue;
        int lp = 0, rp = find(begin(t), end(t), '=') - begin(t) + 1;
        if(rp == 1 || rp == n || checked.count(t) == 1) continue;

        checked.insert(t);

        try {
            auto lval = expr(t, lp), rval = expr(t, rp);
            if(t[lp] == '=' && rp == n && abs(lval - rval) < eps) {
                ans += 1;
            }
        } catch(...) {
            continue;
        }
    } while(next_permutation(begin(v), end(v)));

    cout << ans << endl;
}

感想

これぞやるだけ問題って感じがする.
ret_type = double になってるのは,01しか現れないけどけど10進数解釈をするんだと勘違いして(しかもそれでサンプルが全部合う),31桁も来ると困るなあと思ったからです.普通に int で良い.