2018-12-10

プログラマーに(？)おすすめしたい素数大富豪

この記事は、プログラマーにオススメしたいゲーム紹介 Advent Calendar 2018 6日目の記事です。

adventar.org

素数大富豪には、いろいろな楽しみ方があります！

素数と出会う
素数判定を頑張る
語呂素数を作る
極める
観戦する

など…

素数好きだけでなく、数学が嫌いだった人も*1、幼稚園児も*2楽しんでます！！

さて、競プロにおなじみの素数といえば…そう！

$\LARGE{ 10 ^ 9 + 7 }$ *3

…は素数大富豪では出せないので*4

$\LARGE{ 998244353 }$

を使ってみましょう！

用意するもの

998244353
91・1001・17・19・2001チェック
4枚7~8桁
KTTQJ, KKTQJ, QJQTK, KTQ9J, 3TQKJ
偶数消費型素数

素数大富豪ver4☆pro☆でcpuと対戦です！

方針

まずは全部出しで手札を2倍化(後攻の場合は合成数出しで2倍化)
2桁カードを使って返す
998244353が揃うまでドロー
いい感じに手札が偏る(？)ので残りで手札を組んで勝つ

1戦目

以下標準的数譜案を使用します。

f:id:tatyam_prime:20181209225824p:plain:w400

tatyam: [23456679JQX]

cpu: [1123389TJX]

まずは3の倍数でない最小の数を出します。(ドローしてからの方がよかったですね)

T: JQ2X3456679|X=2,P(124779TQKKK)

C: XJ=3*19*23|X=K

f:id:tatyam_prime:20181209230817p:plain:w600

T: D(5)KK=K*T1

C: D(8)%

f:id:tatyam_prime:20181209231658p:plain:w600

まだ揃ってないのでグロタンチェンジです！*5

T: D(5)57[GC]

f:id:tatyam_prime:20181209232001p:plain:w600

ドローして揃いました！

T: D(3)99X244353|X=8

C: D(2)%

f:id:tatyam_prime:20181209232133p:plain:w450

TTQQが使いにくいのでもう1度です！

T: D(6)TTJQQ6667#

f:id:tatyam_prime:20181209232244p:plain:w400

おっと、出会い素数で勝利です！

2戦目

T: [344578TTJKX]

C: [1357889TJQQ]

T: D(Q)TTJXQK344587,P(122345678TKX)

C: 7QTQJ

f:id:tatyam_prime:20181209232945p:plain:w750

24枚の手札を利用して、5枚10桁で応戦です！

T: D(2)KTTQJ

C: D(6)%

f:id:tatyam_prime:20181209233148p:plain:w650

いまです！

T: D(9)9X8244353|X=9

C: D(9)%

f:id:tatyam_prime:20181209233607p:plain:w500

一番大きい4枚出し: 8QTK から考えて…

グロタンカット: 57

偶数消費4枚: 6421, 6427, 2221

偶数消費3枚: 64X, 22X (X=1,3,7)

T: D(2)6421

C: D(1)9866,P(69JK)

T: 8XTK|X=Q

C: D(9)%

T: 57[GC]

f:id:tatyam_prime:20181209234241p:plain:w450

T: 227#

やりました！！勝利です！

まとめ

998244353、素数大富豪でかなり使えるのではないですか？*6

*1:素数大富豪のおかげで数学アレルギーが治ったら生きるのが楽しい話 - ささやかなふみ川

*2:ちびっこでもできる！素数大富豪の話 - 狐草子

*3: $10 ^ 9 + 7$ と $10 ^ 9 + 9$ は双子素数です。

*4:これをエデンの園素数と言います

*5:ドロー→グロタンカット→ドローの流れのこと

*6:そもそも全部出し→大量出し戦法が強いだけでは()

2018-12-09

JOI予選 2018-2019 参加記録

注意事項

マクロを省略しています。マクロの内容はこちら

A - ソーシャルゲーム (Social Game)

急いで読むと問題が複雑に思えてくるのでシミュレーションを構築

提出1 WA

signed main(){
    LL(a,b,c);
    rep(i,1,c+1000){
        c-=a;
        if(i%7==0)c-=b;
        if(c<=0)return out(i);
    }
}

途中でcの値が変わってしまうのでWA

提出3 AC

1度落ち着いて割り算を構築

signed main(){
    LL(a,b,c);
    ll seven=a*7+b;
    ll ans=c/seven*7;
    c%=seven;
    if(c>a*6)return out(ans+7);
    out(ans+(c+a-1)/a);
}

B - すごろくと駒 (Sugoroku and Pieces)

読んですぐにシミュレーションだなと思う

提出2 AC

signed main(){
    LL(n);
    VEC(ll,x,n);
    x.push_back(2020); // 番兵を置く
    LL(m);
    rep(m){
        LL(a);
        if(x[a]-1>x[a-1])x[a-1]++;
    }
    rep(n)out(x[i]);
}

C - マルバツスタンプ (Circle Cross Stamps)

OXが隣り合っているところを順番に数えれば良さそう(貪欲になることを自明として見ていますね)

提出4 AC

signed main(){
    LL(n);
    STR(s);
    ll ans=0;
    rep(s.size()-1){
        if(s[i]!=s[i+1]){
            ans++;
            i++; // 隣り合っていたら1つ読み飛ばす
            continue;
        }
    }
    out(ans);
}

D - 日本沈没 (Japan Sinks)

日本沈没！？

シミュレーションを工夫して数えるだけ、はー気合い入れたのにDPじゃないのかー。

最初日本が1つの島だと考えて、低い区間から順番に沈めていって、隣の区間が沈んでいるかどうかで島の数が増えるかを判断します。

両方陸の時

□□□□□　→　□□■□□　　増える

片方陸の時

□□□■□　→　□□■■□　　同じ

両方海の時

□■□■□　→　□■■■□　　減る

計算量は $O ( N )$ です。

提出5 WA

signed main(){
    LL(n);
    vec(bool,sink,n);
    vec(pll,a,n);
    rep(n){
        LL(b);
        a[i]={b,i}; // pairに位置情報を入れてからソート
    }
    sort(range(a));
    ll island=1,ans=1;
    rep(n){
        sink[a[i].second]=1;
        island++; // 1度増やしてから、隣の海の分減らす
        if(!a[i].second||sink[a[i].second-1])island--;
        if(a[i].second==n-1||sink[a[i].second+1])island--;
        if(i+1!=n&&a[i].first==a[i+1].first)continue; // 高さが同じ分は同時に処理する
        update_max(ans,island);
    }
    out(ans);
}

4ケースWA、制約をよく見るとすでに日本沈没している場合が存在して、その場合は0を出力しないといけないらしい。

提出6 AC

変更

signed main(){
    LL(n);
    vec(bool,sink,n);
    vec(pll,a,n);
    ll sum=0;
    rep(n){
        LL(b);
        sum+=b;
        a[i]={b,i};
    }
    if(!sum)return out(0);
    ：
    ：
    ：

E - イルミネーション (Illumination)

それぞれの木について入っている区間を持つ？
とりあえず紙に書いて考えよう
ある木を飾り付けると、ある区間が飾れなくなる
それは前計算できそう
その木を飾った時にどこまで飾れなくなるかの配列を作ってナップサックDP

計算量はソート + $O ( N + M )$ です。

提出7 AC

ll n,m;
vector<ll>a,jump,mem;
ll dp(ll at){
    if(at==n)return 0;
    if(mem[at]!=-LINF)return mem[at];
    if(jump[at]==-1)return mem[at]=dp(at+1)+a[at];
    return mem[at]=max(dp(at+1),dp(jump[at])+a[at]);
}
signed main(){
    in(n,m);
    a.resize(n);
    jump.assign(n,-1);
    mem.assign(n,-LINF);
    in(a);
    VEC(pll,duzzle,m);
    sort(range(duzzle));
    ll mx=duzzle[0].second,at=0;
    rep(i,duzzle[0].first-1,n){
        while(at<m-1&&duzzle[at+1].first-1<=i){
            update_max(mx,duzzle[at+1].second);
            at++;
        }
        if(mx>i)jump[i]=mx;
    }
    out(dp(0));
}

F - 座席 (Seats)

$O ( N ^ 4 )$ か？なにもわからない。とりあえずnext_permutationを使って6点

まとめ

ABCDEf 506点でした。Dが簡単だったのでボーダーが400を超えるかなー？と思っています。

春合宿に行きたい！！！

tatyam’s blog

(ﾉ) - ω - (ヾ)ﾓﾁﾓﾁ