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らしくないなあと感じました。
ベクトル解析でdivとかrotを2つ繋げるやつ
$\mathrm{rot}\,\mathrm{grad}\,φ=\mathbf{0}$みたいなやつが微妙に覚えられないのでまとめます
続きを読むJOI春合宿にいくために
この記事は、沖縄アドベントカレンダー2016 22日目の記事です
続きを読む