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

競プロに逃げすぎてレポートが進みません。

問題概要

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

文字列 が与えられる。各文字を、同じ文字は同じ数字・違う文字は違う数字になるように '1', '3', '5', '7', '9' のいずれかに変換する。文字列を素数に変換できるならばその素数を出力し、できないならば -1 を出力せよ。

解説

map と permutation を使って全探索するだけです。next_permutation とかそんなに使わないので備忘録的に書きました。

文字列を反転させておくことで計算が楽になります。文字列から数字にしたりとか、桁数がやたら多かったりとかするときはこれで幸せになることが多い気がします。

ソースコード

bool isprime(int n) {
    if(n == 1) return false;
    for(int i=2; i*i<=n; i++) {
        if(!(n%i)) return false;
    }
    return true;
}

signed main() {
    string s; cin >> s;
    map<char, int> m;
    int cnt = 0;
    reverse(s.begin(), s.end());
    rep(i,0,s.length()) {
        if(!m.count(s[i])) {
            m[s[i]] = cnt++;
        }
    }

    if(cnt > 5) {
        cout << -1 << endl;
        return 0;
    }
    int a[] = {1, 3, 5, 7, 9};
    do {
        int d = 1;
        int num = 0;
        rep(i,0,s.length()) {
            num += d * a[ m[s[i]] ];
            d *= 10;
        }
        if(isprime(num)) {
            cout << num << endl;
            return 0;
        }
    }while(next_permutation(a, a+5));
    cout << -1 << endl;
    return 0;
}