並べ替え最大素数の探索アルゴリズム

素数大富豪が考案されてから約4年半、数々の素数大富豪研究やツールが生まれ、競技者レベルも劇的に向上しました。

並べ替え最大素数の探索プログラムもかなりの人が書いていますが、うまく最大を出してくれるアルゴリズムはなかなかありませんでした。

かなり効率的な並べ替え最大素数の探索アルゴリズムができたので紹介しようと思います。*1

追記

読みにくいのでこっちを見てね

https://drive.google.com/open?id=1heC6qFs6JHj93rMGNclI8z7IQeHd6FWI

ここで問題

カードの枚数 N とカードの内容 A_1\cdots\ A_N が与えられます。

並べ替え最大素数を出力してください。素数にならない場合は -1 を出力してください。

  • 制約

入力は整数で与えられます。

1≤N≤100

0≤A_i≤13

主な方針

  • 3の倍数の場合 -1 を出力
  • 何が何枚あるかの配列に変換して重複を避ける
  • 大きいほうから並べ替えを作って素数判定をする
  • 2か5の倍数になりそうな場合を飛ばす
  • 11の倍数になりそうな場合を飛ばす

よくある嘘解法

  • 9 → 8 → 7 → 6 → 5 → 4 → 3 → 2 → K → Q → J → 1 → T → 0 の順に優先してカードを取っていく

以下、コードはC++(Clang)とboostを使用します。

#include <iostream>
#include <vector>
#include <string>
#include <boost/multiprecision/miller_rabin.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost::multiprecision;

const vector<int> priority = {9, 8, 7, 6, 5, 4, 3, 2, 13, 12, 11, 1, 10, 0};
bool permsearch(int n, cpp_int num, vector<int>& cards) {
    if (n == 0) { // 並べ終えたら素数判定
        if (miller_rabin_test(num, 50)) {
            cout << num << endl;
            return true;
        }
        return false;
    }
    if (cards[1] + cards[3] + cards[7] + cards[9] + cards[11] + cards[13] == 0) return false; // 2・5の倍数の判定
    if (n == cards[10] + cards[11] + cards[12] + cards[13]) { // 1桁がない場合 11の倍数の判定
        int eleven = int(ans % 11);
        eleven += cards[10] * 10 + cards[12] + cards[13] * 2;
        eleven %= 11;
        if (eleven == 0) return false;
    }
    for (auto &i: priority) if (cards[i]) { // 並べる
        cards[i]--;
        if (permsearch(n - 1, num * (i < 10 ? 10 : 100) + i, cards)) return true;
        cards[i]++;
    }
    return false;
}

int main() {
    int n;
    cin >> n;
    if (n == 1) { // 2・3・5を排除しておく
        int a;
        cin >> a;
        if (miller_rabin_test(a, 50)) cout << a << endl;
        else puts("-1");
        return 0;
    }
    vector<int> cards(14);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        cards[a]++;
        sum += a;
    }
    if (sum % 3 == 0) return puts("-1") & 0; // 3の倍数の判定
    if (!permsearch(n, 0, cards)) puts("-1");
}

一見いけるように思える

WA 1ms

input

5
1 7 7 9 13

output

971371

answer

971713

K より 17 の方が大きいんだよね。

ちょっと工夫してみる

  • 9 → 8 → 7 → 6 → 5 → 4 → 3 → 2 → 19 → 18 → 17 → 16 → 15 → 14 → 13 → 12 → 11 → 10 → 1 → 0 の順に優先してカードを取っていく
#include <iostream>
#include <vector>
#include <string>
#include <boost/multiprecision/miller_rabin.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost::multiprecision;

const vector<int> priority = {9, 8, 7, 6, 5, 4, 3, 2, 19, 18, 17, 16, 15, 14, 13, 12, 11, 1, 10, 0};
bool permsearch(int n, cpp_int num, vector<int>& cards) {
    if (n == 0) {
        if (miller_rabin_test(num, 50)) {
            cout << num << endl;
            return true;
        }
        return false;
    }
    if (cards[1] + cards[3] + cards[7] + cards[9] + cards[11] + cards[13] == 0) return false; // 2・5の倍数の判定
    if (n == cards[10] + cards[11] + cards[12] + cards[13]) { // 1桁がない場合 11の倍数の判定
        int eleven = int(ans % 11);
        eleven += cards[10] * 10 + cards[12] + cards[13] * 2;
        eleven %= 11;
        if (eleven == 0) return false;
    }
    for (auto &i: priority) if (i <= 13 && cards[i]) { // 1枚並べる
        cards[i]--;
        if (permsearch(n - 1, num * (i < 10 ? 10 : 100) + i, cards)) return true;
        cards[i]++;
    } else if (i >= 10 && cards[1]) { // 2枚並べる
        cards[1]--;
        if (cards[i - 10]) {
            cards[i - 10]--;
            if (permsearch(n - 2, num * 100 + i, cards)) return true;
            cards[i - 10]++;
        }
        cards[1]++;
    }
    return false;
}

int main() {
    int n;
    cin >> n;
    if (n == 1) { // 2・3・5を排除しておく
        int a;
        cin >> a;
        if (miller_rabin_test(a, 50)) cout << a << endl;
        else puts("-1");
        return 0;
    }
    vector<int> cards(14);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        cards[a]++;
        sum += a;
    }
    if (sum % 3 == 0) return puts("-1") & 0; // 3の倍数の判定
    if (!permsearch(n, 0, cards)) puts("-1");
}

まだ足りない

WA 1ms

input

3
1 11 13

output

11131

answer

11311

どうやら 1 と J があるときにうまくいかないらしい

1 と J を両方判定

  • 9 → 8 → 7 → 6 → 5 → 4 → 3 → 2 → 19 → 18 → 17 → 16 → 15 → 14 → 13 → 12 → (1, 11) → 10 → 0 の順に優先してカードを取っていく
#include <iostream>
#include <vector>
#include <string>
#include <boost/multiprecision/miller_rabin.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost::multiprecision;

const vector<int> priority = {9, 8, 7, 6, 5, 4, 3, 2, 19, 18, 17, 16, 15, 14, 13, 12, 1, 10, 0};
cpp_int permsearch(int n, cpp_int num, vector<int>& cards) {
    if (n == 0) {
        if (miller_rabin_test(num, 50)) return num;
        return -1;
    }
    if (cards[1] + cards[3] + cards[7] + cards[9] + cards[11] + cards[13] == 0) return -1; // 2・5の倍数の判定
    if (n == cards[10] + cards[11] + cards[12] + cards[13]) { // 1桁がない場合 11の倍数の判定
        int eleven = int(num % 11);
        eleven += cards[10] * 10 + cards[12] + cards[13] * 2;
        eleven %= 11;
        if (eleven == 0) return -1;
    }
    cpp_int a = -1;
    for (auto &i: priority) if (i == 1) { // 1とJの大きい方を選ぶ
        cpp_int b = -1;
        if (cards[1]) {
            cards[1]--;
            a = permsearch(n - 1, num * 10 + 1, cards);
            cards[1]++;
        }
        if (cards[11]) {
            cards[11]--;
            b = permsearch(n - 1, num * 100 + 11, cards);
            cards[11]++;
        }
        if (a != -1 || b != -1) return max(a, b);
    } else if (i <= 13 && cards[i]) { // 1枚並べる
        cards[i]--;
        if ((a = permsearch(n - 1, num * (i < 10 ? 10 : 100) + i, cards)) != -1) return a;
        cards[i]++;
    } else if (i >= 10 && cards[1]) { // 2枚並べる
        cards[1]--;
        if (cards[i - 10]) {
            cards[i - 10]--;
            if ((a = permsearch(n - 2, num * 100 + i, cards)) != -1) return a;
            cards[i - 10]++;
        }
        cards[1]++;
    }
    return -1;
}

int main() {
    int n;
    cin >> n;
    if (n == 1) { // 2・3・5を排除しておく
        int a;
        cin >> a;
        if (miller_rabin_test(a, 50)) cout << a << endl;
        else puts("-1");
        return 0;
    }
    vector<int> cards(14);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        cards[a]++;
        sum += a;
    }
    if (sum % 3 == 0) return puts("-1") & 0; // 3の倍数の判定
    cout << permsearch(n, 0, cards) << endl;
}

最悪指数時間かかりそう

AC 1267 ms

input

14
4 6 1 1 1 1 1 1 11 11 11 11 11 11

output

46111111111111111111

answer

46111111111111111111
  • 1 と J がたくさんあると、1 と J を並べ替え続けて同じ数をずっと判定してしまう。

Nヶ月考えた結果

  • priority_queue を使って最大になりそうなものから順に繋げていくといい感じ
  • priority_queue に {繋いだ文字列, 0~Kの残り枚数} を入れる
  • 先頭の数が大きいほど優先で、先頭の数が同じなら短い方を優先する
  • 1を何個繋げるかを全通り試して次に1を繋げられないようにする
  • hash_map に {繋いだ文字列, 0~Kの残り枚数} を保存して、繰り返しを避ける

とすると同じ数を2度数えることなく、上から順に数えられそう。

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <boost/unordered_set.hpp>
#include <boost/multiprecision/miller_rabin.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost::multiprecision;
template <class T> using pq = priority_queue<T, vector<T>, greater<T>>;



boost::unordered_set<pair<string, vector<int>>> mem;
pq<tuple<string, int, vector<int>, cpp_int>> que;
inline string reverse(string s) {
    for (char &i : s) {
        i = 154 - i;
    }
    return s;
}
inline char reverse(char c) {
    return 154 - c;
}
inline void check(string num, int n, vector<int> &cards, cpp_int ans){ // priority_queueに入れる前にチェックすると計算量削減?
    if (mem.count({num, cards})) return; // 重複判定
    mem.insert({num, cards});
    if (n == 0){
        que.push({num, n, cards, ans});
        return;
    }
    if (cards[1] + cards[3] + cards[7] + cards[9] + cards[11] + cards[13] == 0) return; // 2・5の倍数の判定
    if (n == cards[10] + cards[11] + cards[12] + cards[13]) { // 1桁がない場合 11の倍数の判定
        int eleven = int(ans % 11);
        eleven += cards[10] * 10 + cards[12] + cards[13] * 2;
        eleven %= 11;
        if (eleven == 0) return;
    }
    if (num.size() && num.back() == reverse('1') && n == cards[1] + cards[11]) return; // 最後が1の場合 1・Jを続けない
    que.push({num, n, cards, ans});
}
int main() {
    int n;
    cin >> n;
    if (n == 1) { // 2・3・5を排除しておく
        int a;
        cin >> a;
        if (miller_rabin_test(a, 50)) cout << a << endl;
        else puts("-1");
        return 0;
    }
    vector<int> cards(14);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        cards[a]++;
        sum += a;
    }
    if (n > 1 && sum % 3 == 0) return puts("-1") & 0; // 3の倍数の判定
    que.push({"", n, cards, 0});
    while (!que.empty()) {
        string num = get<0>(que.top());
        int n = get<1>(que.top());
        vector<int> cards = get<2>(que.top());
        cpp_int ans = get<3>(que.top());
        que.pop();
        if (n == 0) { // 素数判定
            if (miller_rabin_test(ans, 50)) {
                cout << reverse(num) << endl;
                return 0;
            }
            continue;
        }
        for (int i = 0; i < 14; i++) if (cards[i] && i != 1 && i != 11) { // 繫げる
            cards[i]--;
            check(num + reverse(to_string(i)), n - 1, cards, ans * (i < 10 ? 10 : 100) + i);
            cards[i]++;
        }
        if (num.back() == reverse('1')) continue; // 最後が1でない場合
        if (cards[1]) { // 1を何個繋げるかを全通り試す
            int one = cards[1];
            while (cards[1] || cards[11]) {
                if (cards[1] != one && cards[11]) {
                    cards[11]--;
                    cards[1]++;
                }
                else {
                    cards[1]--;
                    n--;
                }
                num += reverse('1');
                ans = ans * 10 + 1;
                check(num, n, cards, ans);
            }
        }
        else while (cards[11]) {
            num += reverse("11");
            n--;
            cards[11]--;
            ans = ans * 100 + 11;
            check(num, n, cards, ans);
        }
    }
    puts("-1");
}

とても速い

AC 3 ms

input

14
4 6 1 1 1 1 1 1 11 11 11 11 11 11

output

46111111111111111111

answer

46111111111111111111

AC 24 ms

input

54
1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 10 10 10 10 11 11 11 11 12 12 12 12 12 13 13 13 13 13

output

999988887777666655554444333322221313131313121212121211111111101110110101

answer

999988887777666655554444333322221313131313121212121211111111101110110101

計算量は?

  • 素数判定  O ( N ^ 2 )
  • 素数が出るまでの判定回数(期待値)  O ( N )

計算量は平均で  O ( N ^ 3 ) (´・ ω ・ `)カナー

拡張性

3桁くらいまでなら比較的簡単に拡張することができる。

これを任意桁にすると倍数判定が大変なことになる。

あとこんな問題も解ける

  • 文字列が  N 個あります。これらを任意の順番で連結してできる文字列を辞書順に  K 個答えてください。

*1:私の素数判定アプリで使っています