らての精進日記

修行をします

日記 20180919

日記を書きます

競技プログラミング

ACPCのday1にチームlatte0119(メンバー:latte0119)の一員として出ました。

Eの貪欲、正当性、なに
F,なに
Gについては、正直writerをブロックしたい
H,なに

うーん、あんまり競技プログラミングしない人間だけど、衰えは感じない(成長も)

ウクニキアについて

うくさんがアズリムタグで長文オタクツイートしてる様子をよく見るので、真似するようになった
まだ錬成に時間がかかる

フォートナイト

そこそこハイセンシにしてプレイしてた(dpi1000、感度xy0.10)
建築は楽だけどエイムがきつい(でも慣れてくるとタクティカルショットガンが使いやすいなあと感じた 逆にポンプが当たらない)

朝一の試合で楽にビクロイした(敵が弱い時間帯)

acpcの後にやけ酒してからまたフォートナイトした 時間帯的に敵のレベルがエぐ過ぎてきつかった


これ結構うまくいった このシーンの前にも結構つらい場面があった(複数人から集中砲火されたり、漁夫がひたすらアサルトライフルで邪魔してきたり)んだけど、いつもみたいになげやりにならずに落ち着いて防御できたと思う 無駄死にしないのは大切

あと二連式ショットガンがちゃんと使えるようになってきたと思う(チート火力なのでつい使いたくなるんだけど、適切な距離とタイミングで撃たないとリスクがでかいので、そこらへんの見極めをするようになってきた 二連式キッズを卒業しよう)

屋根もちょいちょい使えるようになってきたよ



うくにきあくんおいしかった?笑

レヴュースタァライトについて

いい

今日は楽しかったですか

ふつう

JOI2017/2018予選

はじめに

うくにきあ

1問目

やる

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
 
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
 
signed main(){
    int N,A,B,C,D;
    cin>>N>>A>>B>>C>>D;
 
    cout<<min((N+A-1)/A*B,(N+C-1)/C*D)<<endl;
    return 0;
}

2問目

連続する1の数+1が答えだとわかるため

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
 
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
 
signed main(){
    int N;
    cin>>N;
    vint A(N);
    rep(i,N)cin>>A[i];
 
    int cur=0;
    int ans=1;
    while(cur<N){
        if(A[cur]==0)cur++;
        else{
            int nex=cur;
            while(nex<N&&A[nex])nex++;
            chmax(ans,nex-cur+1);
            cur=nex;
        }
    }
    cout<<ans<<endl;
    return 0;
}

3問目

O(H^2 W^2)で全探索する。なんかもはや2問目の方が難しいんじゃないか

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
 
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
 
int H,W;
int A[33][33];
 
signed main(){
    cin>>H>>W;
    rep(i,H)rep(j,W)cin>>A[i][j];
 
    int ans=LLONG_MAX;
    rep(i,H)rep(j,W){
        int sum=0;
        rep(k,H)rep(l,W){
            sum+=min(abs(i-k),abs(j-l))*A[k][l];
        }
        chmin(ans,sum);
    }
    cout<<ans<<endl;
    return 0;
}

4問目

dp[i][j]:=i番目の切れ目までの切り方を確定させて、i番目の切れ目で切ることにして、かつこれまでの長さの最大値がjであるときの、"これまでの長さの最小値"の最大値、とする。

まあ下に貼ったコードのように遷移するとO(N^3 L) (L=max{L_i})で解ける。O(N^2L)とかでも解けるんだろうか、うーん

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
 
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
 
const int INF=1231231231231231231ll;
 
int N;
int L[55];
 
int dp[55][55555];
 
signed main(){
    cin>>N;
    rep(i,N)cin>>L[i+1];
    rep(i,N)L[i+1]+=L[i];
 
    memset(dp,-1,sizeof(dp));
    dp[0][0]=INF;
 
    for(int i=0;i<N;i++){
        for(int j=0;j<L[N];j++){
            if(dp[i][j]==-1)continue;
            for(int k=i+1;k<=N;k++){
                chmax(dp[k][max(j,L[k]-L[i])],min(dp[i][j],L[k]-L[i]));
            }
        }
    }
 
    int ans=INF;
    for(int i=0;i<L[N];i++)if(dp[N][i]!=-1)chmin(ans,i-dp[N][i]);
    cout<<ans<<endl;
    return 0;
}

5問目

dp[k][i][j]=座標(i,j)の木を切り終えて、(0,0)から(i,j)まで長さkの道を歩んできたときの時間の最小値、とする。
まあ普通に4近傍に遷移していい感じにできるため、おわり。
下のコードではdijkstraしてますが、遷移がDAGになっているためふつうにdpでいいです。(気付かなかった)

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
 
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
 
const int INF=1231231231231231231ll;
 
int H,W;
int A[33][33];
 
int dist[33][33][33*33];
 
using Taplis=tuple<int,int,int>;
 
int dy[4]={-1,0,1,0};
int dx[4]={0,-1,0,1};
 
signed main(){
    cin>>H>>W;
    rep(i,H)rep(j,W)cin>>A[i][j];
 
    fill_n(**dist,33*33*33*33,INF);
    dist[0][0][0]=0;
    priority_queue<Taplis,vector<Taplis>,greater<Taplis>>que;
    que.push(make_tuple(0,0,0));
 
    int ans=INF;
    while(que.size()){
        int z,y,x,c,d;
        tie(c,z,d)=que.top();
        que.pop();
        y=z/W;
        x=z%W;
        if(dist[y][x][d]<c)continue;
 
        if(y==H-1&&x==W-1){
            cout<<c<<endl;
            return 0;
        }
 
        if(d+1==H*W)continue;
 
        rep(dir,4){
            int ny=y+dy[dir];
            int nx=x+dx[dir];
            if(ny<0||ny>=H||nx<0||nx>=W)continue;
            int nd=d+1;
            int nc=c+(2*d+1)*A[ny][nx];
            if(dist[ny][nx][nd]<=nc)continue;
            dist[ny][nx][nd]=nc;
            que.push(make_tuple(nc,ny*W+nx,nd));
 
        }
    }
 
    cout<<ans<<endl;
    return 0;
}

6問目

最終的にJOI君(そういう名前じゃなかったかも)が得る数列(以下、最終数列と呼ぶ)のL番目がZであったとする。(このZが答え)

C(x):=最終数列における、x以下の値の数がL個以上ならtrue、そうでないならfalse
とすると、Zは、C(x)がtrueとなる最小のxに等しいとわかる。

また、C(x)には単調性があるため、結局二分探索すればいい。
あとは判定関数Cをどうやって実装するんですか?という話なんですけど、まあとりあえずO(N)で実装できます(完)
よって全体でO(NlogN)で解けた。

判定関数を実装するときのコツなんですけど、"ある数列のK番目の値がk以下"⇔"その数列にはk以下の数がK個以上含まれている"
と言い換えると見通しがよくなるかもしれません。

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
 
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
 
int N,K,L;
int A[222222];
 
bool C(int val){
    int r=N;
    int c=0;
 
    int cnt=0;
    for(int i=N-1;i>=0;i--){
        if(A[i]<=val)c++;
        while(c-(A[r-1]<=val)>=K){
            c-=A[r-1]<=val;
            r--;
        }
 
        if(c>=K)cnt+=N-r+1;
    }
    return cnt>=L;
}
 
signed main(){
    cin>>N>>K>>L;
    rep(i,N)cin>>A[i];
 
    int lb=0,ub=N;
    while(ub-lb>1){
        int mid=(ub+lb)/2;
        if(C(mid))ub=mid;
        else lb=mid;
    }
    cout<<ub<<endl;
    return 0;
}

おわりに

難易度についてですが、去年よりは難しかった気がします。
というか、個人的に4問目がそこそこ難しいと感じました。
あと6問目はあまりJOIらしくないなあと感じました。