東京工業大学プログラミングコンテスト2015 D - 文字列と素数

東京工業大学プログラミングコンテストに参加しました。
かなり良い問題ばかりでとても楽しかったです。できればもうちょっと良い順位を取りたかった…

問題

ttpc2015.contest.atcoder.jp

解法

S に 5 種類より多い文字があるとサンプルにある通り奇数を対応させきることができなくなるので迷わず NG です。

5 種類以下の文字しかない場合, それぞれの文字に対して奇数を対応させるのを全探索します。

1 が素数でないことに注意。

int odd[] = {1, 3, 5, 7, 9};

bool prime(ll p) {
    if (p == 1) return false;
    for (ll i = 2; i * i <= p; i++) {
        if (p%i == 0) return false;
    }
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int n = s.size();
    vector<char> app;
    for (char c : s) {
        if (find(app.begin(), app.end(), c) != app.end()) continue;
        else app.push_back(c);
    }
    if (app.size() > 5) {
        cout << -1 << endl;
        return 0;
    }
    int size = app.size();
    vector<int> perm(5);
    for (int i = 0; i < 5; i++) perm[i] = i;
    do {
        string t = s;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < n; j++) {
                if (app[i] == t[j]) t[j] = (char)('0'+odd[perm[i]]);
            }
        }
        ll p = stoll(t);
        if (prime(p)) {
            cout << p << endl;
            return 0;
        }
    } while (next_permutation(perm.begin(), perm.end()));
    cout << -1 << endl;
    return 0;
}