Send More Money [AtCoder Beginner Contest 198 D]

https://atcoder.jp/contests/abc198/tasks/abc198_d

解説

https://atcoder.jp/contests/abc198/submissions/21692252

覆面算のソルバーを普通に作る。
各文字にその数字を割り当てるかを全探索で決めていこう。
各文字にどの数字を割り当てるかということを考えると順列を作っているような感じになる。
順列の全探索に用いるのはdfsなので、dfsで頑張る。

dfsに入る前に使われている文字を集計して、被りなしの個数を見ておこう。
10個までなら数字を割り当て可能だが、それを超えると無理なのでUNSOLVABLEで答える。

dfs関数

dfs(cu) := cu番目の文字まで確定させている状態で入ってくる

全列挙の形は自然な形であるのでdfsの学習をしていれば理解できるだろう。
各文字について0～9の数字を割り当てる。
それまでに使われていればスキップして、使われてなければ割り当ててdfsを1階層進めて、戻ってきたら割り当てを解除する。
最下層まで来たらcheck関数でチェックしよう。

check関数

チェック関数では以下のことをチェックする。

• to_stringとstollを使って、leading-zero（先頭に0が無いか）をチェックする。先頭に余分な0があればダメ
• S1+S2=S3となっているか
• S1,S2,S3が0でない、正の整数であることを確認

全部満たしていれば答えとする。

間に合う？

最大で10!通りの組み合わせなので、結構厳しい。
判定関数もだいぶ雑に書いたのでやや重い。
しかし、問題の実行時間制限を見ると5secとあるので、ややギリギリになることは想定されているように見える。
後は競プロで重要な祈りの力を込めて出すと通る。
（ちなみに、有名なkenkooooさんは祈りを込めてソースコードに仏像を建造している）

string S1, S2, S3;
#define NOANS "UNSOLVABLE"
//---------------------------------------------------------------------------------------------------
vector<char> chars;
char used[10];
bool check() {
    map<char, char> mapping;
    rep(i, 0, 10) if (used[i] != 0) mapping[used[i]] = char('0' + i);

    string SS1, SS2, SS3;
    fore(c, S1) SS1 += mapping[c];
    fore(c, S2) SS2 += mapping[c];
    fore(c, S3) SS3 += mapping[c];

    if (to_string(stoll(SS1)) != SS1) return false;
    if (to_string(stoll(SS2)) != SS2) return false;
    if (to_string(stoll(SS3)) != SS3) return false;
    if (stoll(SS1) + stoll(SS2) != stoll(SS3)) return false;
    if (stoll(SS1) == 0) return false;
    if (stoll(SS2) == 0) return false;
    if (stoll(SS3) == 0) return false;

    cout << SS1 << endl;
    cout << SS2 << endl;
    cout << SS3 << endl;
    return true;
}
bool dfs(int cu) {
    if (cu == chars.size()) return check();

    rep(i, 0, 10) if (used[i] == 0) {
        used[i] = chars[cu];
        if (dfs(cu + 1)) return true;
        used[i] = 0;
    }

    return false;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S1 >> S2 >> S3;

    fore(c, S1) chars.push_back(c);
    fore(c, S2) chars.push_back(c);
    fore(c, S3) chars.push_back(c);
    sort(all(chars));
    chars.erase(unique(all(chars)), chars.end());

    if (10 < chars.size()) {
        cout << NOANS << endl;
        return;
    }

    bool res = dfs(0);
    if (res == false) cout << NOANS << endl;
}