たくさんの八方美人たち
この記事は 素数大富豪 Advent Calendar 2019 20日目の記事です。
素数大富豪研究会でポスター発表をしてきました。 tatyam です。
ポスター置いときますね(⊃ ´ ꒳ ` )⊃ drive.google.com
ポスター発表してよかった🤗🤗
八方美人素数
八方美人素数は、第3回日曜数学会 in 札幌 で OTTY さんが発表したものが初出だと思っています。
一度に8つもの素数を覚えることのできる素晴らしい素数で、発表の後九方美人素数が発見されたりしました。
A=16,B=194633が九方美人になる組でした!(3の倍数でないxについてAxBはすべて素数になります)
— ぽかーん懐古DP@259家(桃音モモ) (@259_Momone) 2018年2月18日
で、これはおぼえるしかない!ということでプログラムを書きました
QK_lib/eightFriendPrimes.cpp at master · tatyam-prime/QK_lib · GitHub
数ヶ月かけて、10枚出しまで八方美人素数を列挙しました。(たぶん 7 の倍数とか 11 の倍数とかも絞ればかなり速くなると思うんですが)
宣伝
(受験が終わったら開発が再開されるかもしれない)私の素数大富豪用素数判定アプリでは、八方美人素数をきれいに表示できます。
Android版が欲しい方はDMまで : tatyam (@tatyam_prime) | Twitter
小さめの八方美人たち
例外があるやつは覚えるコストが追加でかかってしまうので、3の倍数以外は全て素数になるものを紹介します。
語呂合わせを募集中(⊃ ´ ꒳ ` )⊃
2X6Q9
上の動画でも紹介されていた
偶数消費型 Xの後ろに3の倍数 * 3
X8JT33
けっこうつよい
J462X51
X62J919
X671573
84Q56X3
偶数消費型
3XJ8637
X = 0 でも素数になる八方美人
423X8243
前に 423, 後ろに 243
159694X63
X = 0 でも素数になる九方美人 (!?)
27359X681
1, 2, 3, 5, 6, 7, 8, 9 を使う八方美人
大きめの八方美人たち
JTJXK191
8 枚 12 ~ 13 桁
T7X7J2QQJ
9 枚 14 ~ 15 桁 九方美人
JJ1X7K2TK
9 枚 14 ~ 15 桁
J6KK2JXKJ
9 枚 15 ~ 16 桁
J 3つ, K 3つ
QJ5T347TX7
10 枚 14 ~ 15 桁 九方美人
15TXQJK32J
10 枚 15 ~ 16 桁
25Q5XJ4KJJ
10 枚 15 ~ 16 桁
9JQK4Q2X3J
10 枚 15 ~ 16 桁
T22JTXKK67
10 枚 15 ~ 16 桁
T75T2TTTX7
使えね〜〜
JT6X6Q37JJ
10 枚 15 ~ 16 桁
J51XT78TQ23
11 枚 15 ~ 16 桁 九方美人
8K3XQT1T4J9
11 枚 16 ~ 17 桁 九方美人
かぶりのない八方美人たち (10枚出し)
126QX8T49
218J5673XK
56T8Q4JX73
九方美人
672J85QXT1
6X9K47582J
6Q5384XT2K
九方美人
7K912Q46XJ
84J95X1K27
九方美人
T46X9K8Q57
J4X9872651
JTX8Q71529
XJQT375269
KJ6T8253X1
マスパーティの素数大富豪大会ジュニアの部決勝戦では何が起こっていたのか
どうも、そろそろ高校生最強を名乗っていいんじゃないでしょうか。 tatyamです。
マスパーティの素数大富豪大会ジュニアの部で優勝してきました。
決勝戦の様子
https://youtu.be/6yPdf4RjZSk?t=34731
今回は、決勝戦の3試合を詳しく解説したいと思います。
1試合目
じゃんけんに勝って奇数試合目の先行になる。
t : (2357899TJQK)
TJQKと2桁が4枚揃った良い手札。 知っていれば 9923 → KTQJ → 857 などで組みきることができる。
た : (6678899TQQK)
若干偏った手札。 何枚か引いて偏りを解消するのがよさそう。
t : 2357
KTQJを切り札にして4枚出しから始める。 残りの 899 は 29 で割れることが分かったがとりあえず出す。 実は 325X が4つ子なのだが、見栄え重視で 2357 を選んだ。
た : D(5) %
ここはなにか出しておきたかった。
t : D(4) 8T49
989 も 23 で割れることが分かっていたが、パスしてくれたので、おそらく返せないだろう4枚出しをする。 8T4X は"八頭身"4つ子である。
た : %
t : QK
残る (9JQK) は3の倍数だったが、パスしてくれたので、さすがに合成数出しはこないやろ!wとみて QK を出す。
た : %
合成数出しをしようにも3枚以上足りないのでどうしようもない。
t : 9J#
ここまで5分
2試合目
た : (15789TQQKKX)
57, ジョーカー, 2桁のある強い手札。
t : (1236689TJJK)
(4枚出し以下がメインの私には)微妙な手札に見える。 5枚出しでは 8JJTK などがある。
た : QK
初手 QK の強気の1手。 89 → QK , T1 → QK で1桁を減らしたほうがよかったかと思う。
t : D(J) KT, P(1K)
初手 QK なので相手の手札が強いことを想定して、手札を補強する。
た : 57[GC]
グロタンカットは後でよかったと思う。 グロタンカットを後回しにすることは、手札情報を減らす意味と選択肢を増やす意味がある。
た : QK
2連続 QK。 やばそう。
t : D(T) KT, P(26)
実はもう KK = 13 * T1 が揃っているのだが、引いた後に気が付いた。
た : T9
t : D(X) KK = 13 * T1
Kは4枚見えているのに強気の手札だったことから、JOKERを持っていると予想。 合成数出しで返す。
ここで手札を再確認
t : (26689TJJJX)
偏りがあって組みにくいて手札。
た : (18X)
t : D(1) 8629
偶数消費型で手札を減らす。*1 "ハム肉"の語呂合わせがある。
た : D(7) 87X1|X=1, P(489Q)
これが素数であれば勝ちだったが、8711 = 31 * 281 と割れてしまう。 9871などが素数になる。
t : D(4) 641
偶数消費型で手札を減らす。 JJJ が使いづらそうだったので3枚出しにしたが、今考えるとJKJJがある。
た : 881
でこぽんさんから聞いたという"ヤバい"3つ子 (881, 883, 887)
t : 2TJ
KJJ を切り札にして 36 + ドロー で上がりたい形
た : D(4) 9QX|X=K
91213 = 53 * 1721 3枚5桁の最大が 8TK であることを知っていればこれは防げる。 ここで残り5分のコール。
t : 3J
準決勝の15分打ち切りが若干トラウマになっていたので最後に素数を組めるように手札をそろえていくことにした。 D(4) → KJJ → 643 の方が良かった。
た : 8J
最後に向けて手札を減らす。
t : D(4)%
まだ何ターンかあるのでドローして様子を見る。
た : Q7
使いづらいQを消費。
t : D(T) 6X|X=K
残りの手札を考えると、JOKERを消費して 6K → 4TJ がよさそう。 若干の遅延行為で時間調整をする。
た : D(3)QX|X=K
残り1分のコールがあり、 残りの (3449) で組める素数を探し、ギリギリまで使って QK を出す。
ここで15分打ち切り
t : 4TJ
た : 4349
たけのこさんも素数を出したが、素数の大きさで私の勝ちとなった。 ちなみに並べ替え最大は 4943。
ここまで24分
3試合目
t : (2333456899T)
2桁の少ない厳しい手札。 決勝が終わってしまう前になにか良い素数を出せないかと探すと 99824 353 を発見する。
た : (11678TJJJQK)
2桁が6枚もある強い手札。 しかし n枚2n桁 などを覚えていないとなかなか活かすのは難しい。
t : D(4) 998244353*2
ここで4を引いてきて「まじ?」とか言ってる。 残りは (36T)、 1063 を判定するが 19 あたりで割れてしまい「なるほど」とか言ってる。
た : KQJJJT861, P(2567789QK)
9枚出しにチャレンジするも、 131211111110861 = 239 * 7321 * 74989819
t : T63#
6103 は 17 で 割れてしまうが、1063 はどこかでみた気がするのでもう一度計算すると、29まで割れないことがわかる。 T63を出して試合終了。
ここまで32分、3勝で私の優勝となった。 winning prime は 1063。
感想
ジュニアの部を開いていただき ☆.。・:+(゚∀゚感謝・感激・雨嵐;;;゚д゚)i||i||||i||i
最後に 998244353 を出せたのは本当にうれしい。
MathPowerルールは1つ見所ができるというのは面白いが、試合時間によってプレイが制限される感じがあった。 持ち時間制の方が好き。
並べ替え最大素数の探索アルゴリズム
素数大富豪が考案されてから約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桁くらいまでなら比較的簡単に拡張することができる。
これを任意桁にすると倍数判定が大変なことになる。
あとこんな問題も解ける
- 文字列が 個あります。これらを任意の順番で連結してできる文字列を辞書順に 個答えてください。
素数大富豪判定アプリを作ってみたお話
この記事は 素数大富豪 Advent Calendar 2018 6日目の記事です。
昨日はbutchi_yさんの「素数大富豪研究のためのMathematicaユーティリティー関数」でした。
素数大富豪研究のためのMathematicaユーティリティー関数 - Qiita
初めまして!
twitterと素数大富豪と競技プログラミングをしている高校生のtatyamと申します。
私からは自作素数判定アプリの紹介をしてみようと思います。
作った経緯
プログラミングしたい!!
↓
Mac買ってもらった!!
↓
アプリ作ろう!!
↓
素数大富豪ディーラー作ろう!!
再現できました
デザインが全部デフォルトで、コードも難しくはないのでできてしまいました。*1
デザインが良くない?
アプリの作り方は分かってきたので作り直し。
電卓を参考にして良い感じにできました。*2
機能
素数判定・素因数分解
入力された数字について素数判定を行います。入力の限界は約20億桁ですが、その前に性能の限界になるでしょう。
素数判定はBigIntegerのisProbablyPrime(Miller-Rabin素数判定法)を利用しています。
これは確率的素数判定法ですが、合成数を素数と判定する確率は よりずっと小さいので問題ないでしょう。計算量はです。
詳細はWikipediaがわかりやすいかと思います。
また、素因数分解にはPollard-Rho法を利用しています。
これすごくないですか??とっても速いです。計算量はです。
Xを入れてまとめて探索
Xを入れて素数判定をすると、Xに0~Kを入れてまとめて判定できます。*3
3つまでXを入れられます。
4つ子も九方美人も1画面に出すことができます。
コックさん素数もまとめて探索できます。
並べ替え最大素数の探索
判定ボタンを長押しすると、並べ替え最大素数を表示してくれます。Xを1つだけ入れることができます。
54枚入れても、1秒はかからない自信があります。(※最新の機種の場合)
計算量はです。*4
タイマー
1手ごとの時間のほか、1人ごとの持ち時間を設定することができます。
今後の予定
- 採譜モードをつくる
素数判定しながら採譜ができるというのを目指しています。
これができたら公開しようかな…?
- iOS版について
実は最低限の部分だけはできています。公開にはApple Developer Program ($99/年) が必要なので支援をいただこうかな?と思っています。*5
フォントが素晴らしい…
さいごに
欲しい!と思っていただけた方、DMお待ちしております。
tatyam@JOIに向けて精進 (@tatyam_prime) | Twitter
すでに持っている方も、もう一度ダウンロードしてアップデートをお願いします。
とあるコンテストに素数大富豪の問題を出すことにしたので解いてほしいなー((o(ΦωΦ+)o))
Advent Calendar Contest 2018 - yukicoder
明日はでこぽんさんの「MathPowerで語呂素数ガチャつくった話」です!.+゚(o(。・д・。)o).+゚ワクワク