並べ替え最大素数の探索アルゴリズム
素数大富豪が考案されてから約4年半、数々の素数大富豪研究やツールが生まれ、競技者レベルも劇的に向上しました。
並べ替え最大素数の探索プログラムもかなりの人が書いていますが、うまく最大を出してくれるアルゴリズムはなかなかありませんでした。
かなり効率的な並べ替え最大素数の探索アルゴリズムができたので紹介しようと思います。*1
追記
読みにくいのでこっちを見てね
https://drive.google.com/open?id=1heC6qFs6JHj93rMGNclI8z7IQeHd6FWI
ここで問題
カードの枚数 とカードの内容 が与えられます。
並べ替え最大素数を出力してください。素数にならない場合は を出力してください。
- 制約
入力は整数で与えられます。
主な方針
- 3の倍数の場合 を出力
- 何が何枚あるかの配列に変換して重複を避ける
- 大きいほうから並べ替えを作って素数判定をする
- 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
計算量は?
計算量は平均で (´・ ω ・ `)カナー
拡張性
3桁くらいまでなら比較的簡単に拡張することができる。
これを任意桁にすると倍数判定が大変なことになる。
あとこんな問題も解ける
- 文字列が 個あります。これらを任意の順番で連結してできる文字列を辞書順に 個答えてください。