2019-12-21

たくさんの八方美人たち

この記事は　素数大富豪 Advent Calendar 2019　20日目の記事です。

adventar.org

素数大富豪研究会でポスター発表をしてきました。 tatyam です。

ポスター置いときますね(⊃ ´ ꒳ ` )⊃ drive.google.com

ポスター発表してよかった🤗🤗

八方美人素数

www.youtube.com

八方美人素数は、第３回日曜数学会 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

2019-10-24

マスパーティの素数大富豪大会ジュニアの部決勝戦では何が起こっていたのか

どうも、そろそろ高校生最強を名乗っていいんじゃないでしょうか。 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の倍数だったが、パスしてくれたので、さすがに合成数出しはこないやろ！ｗとみて 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つ見所ができるというのは面白いが、試合時間によってプレイが制限される感じがあった。持ち時間制の方が好き。

*1:http://mathingnow.hatenablog.com/entry/2017/12/18/121300

*2:https://twitter.com/kirika_comp/status/992235106088636417

2019-02-01

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

素数大富豪が考案されてから約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

answer

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

answer

どうやら 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:私の素数判定アプリで使っています

2018-12-04

素数大富豪判定アプリを作ってみたお話

この記事は素数大富豪 Advent Calendar 2018 6日目の記事です。

adventar.org

昨日はbutchi_yさんの「素数大富豪研究のためのMathematicaユーティリティー関数」でした。

素数大富豪研究のためのMathematicaユーティリティー関数 - Qiita

初めまして！

twitterと素数大富豪と競技プログラミングをしている高校生のtatyamと申します。

私からは自作素数判定アプリの紹介をしてみようと思います。

作った経緯

プログラミングしたい！！

　　　　↓

Mac買ってもらった！！

　　　　↓

アプリ作ろう！！

　　　　↓

素数大富豪ディーラー作ろう！！

再現できました

デザインが全部デフォルトで、コードも難しくはないのでできてしまいました。*1

デザインが良くない？

アプリの作り方は分かってきたので作り直し。

電卓を参考にして良い感じにできました。*2

機能

素数判定・素因数分解

入力された数字について素数判定を行います。入力の限界は約20億桁ですが、その前に性能の限界になるでしょう。

素数判定はBigIntegerのisProbablyPrime(Miller-Rabin素数判定法)を利用しています。

これは確率的素数判定法ですが、合成数を素数と判定する確率は $4^{-100}$ よりずっと小さいので問題ないでしょう。計算量は $O(\log ^2N)$ です。

詳細はWikipediaがわかりやすいかと思います。

ミラー–ラビン素数判定法 - Wikipedia

また、素因数分解にはPollard-Rho法を利用しています。

ポラード・ロー素因数分解法 - Wikipedia

これすごくないですか？？とっても速いです。計算量は $O(N^{\frac{1}{4}}\log ^2N)$ です。

Xを入れてまとめて探索

Xを入れて素数判定をすると、Xに0~Kを入れてまとめて判定できます。*3

3つまでXを入れられます。

4つ子も九方美人も1画面に出すことができます。

コックさん素数もまとめて探索できます。

並べ替え最大素数の探索

判定ボタンを長押しすると、並べ替え最大素数を表示してくれます。Xを1つだけ入れることができます。

54枚入れても、1秒はかからない自信があります。(※最新の機種の場合)

計算量は $O(\log ^3N)$ です。*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).+ﾟﾜｸﾜｸ

*1:ここまで3ヶ月くらい、機能追加に4ヶ月くらい(※常に進捗を出していたわけではないため参考値です)

*2:作り直してから3ヶ月、かなり完成度は高まりました。

*3:革新的ではありませんか？私はそう思います。

*4:詳細はあとで公開しようと思っています。

*5:実機テストは出来るのですが、7日で動かなくなります。

tatyamのそすーブログ

そすー！

たくさんの八方美人たち

八方美人素数

宣伝

小さめの八方美人たち

大きめの八方美人たち

かぶりのない八方美人たち (10枚出し)

マスパーティの素数大富豪大会ジュニアの部決勝戦では何が起こっていたのか

決勝戦の様子

1試合目

2試合目

3試合目

感想

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

追記

ここで問題

主な方針

よくある嘘解法

一見いけるように思える

ちょっと工夫してみる

まだ足りない

1 と J を両方判定

最悪指数時間かかりそう

Nヶ月考えた結果

とても速い

計算量は？

拡張性

素数大富豪判定アプリを作ってみたお話

作った経緯

再現できました

デザインが良くない？

機能

素数判定・素因数分解

Xを入れてまとめて探索

並べ替え最大素数の探索

タイマー

今後の予定

さいごに