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

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