らての精進日記

修行をします

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らしくないなあと感じました。

aoj2564:Tree Reconstruction

続きを読む

ベクトル解析でdivとかrotを2つ繋げるやつ

$\mathrm{rot}\,\mathrm{grad}\,φ=\mathbf{0}$みたいなやつが微妙に覚えられないのでまとめます

続きを読む

JOI2017本選

f:id:latte0119:20161222003033j:plain

aojに問題が上がった時のためにコードを保存しておきます

続きを読む

JOI春合宿にいくために

この記事は、沖縄アドベントカレンダー2016 22日目の記事です

続きを読む