joi2018 本選
はじめに
うくにきあ ちょっと変えると やきにくや
1問目 STOVE
貪欲します
予想難易度:5
#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,K; cin>>N>>K; vint T(N); rep(i,N)cin>>T[i]; int ans=T.size(); vint lis; for(int i=0;i+1<T.size();i++)lis.pb({T[i+1]-T[i]-1}); sort(all(lis)); rep(i,N-K)ans+=lis[i]; cout<<ans<<endl; return 0; }
2問目 ART
やるだけ
類題:
cf17-relay-open.contest.atcoder.jp
予想難易度:5.5
#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 S1[555555]; int S2[555555]; signed main(){ int N; cin>>N; vpint A; rep(i,N){ int a,b;cin>>a>>b; A.pb({a,b}); } sort(all(A)); for(int i=0;i<N;i++){ S1[i+1]=S1[i]+A[i].se; } rep(i,N)S1[i+1]-=A[i].fi; for(int i=0;i<N;i++){ S2[i+1]=S2[i]+A[i].se; S2[i]-=A[i].fi; } int ans=0; int mi=S2[0]; for(int i=1;i<=N;i++){ chmax(ans,S1[i]-mi); chmin(mi,S2[i]); } cout<<ans<<endl; return 0; }
3問目 Dango Maker
これかなり良問だと思います。
マス目中の各Gに対して、次の3つのうち1つを割り当てます
1.横方向の団子の真ん中としてつかう
2.縦方向の団子の真ん中としてつかう
3.つかわない
これらは独立に決めてもよいでしょうか？だめです
しかし、斜め方向の各ラインごとに独立に決めていいことはわかります。
(
XXY
XGX
YXX
上のようになっていたとして、真ん中のGの割り当てを決めたときに、影響を及ぼすのはYの位置にあるGだけなのです)
よって、斜め方向の各ラインについてdpをすると、O(NM)で解ける
予想難易度:8(ちょっと過大評価しすぎ？でも考察が面白いし、個人的に9でもそこまで違和感を感じない)
#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; string S[3333]; int dp[3333][2]; int solve(int y,int x){ vint v; for(int k=0;y-k>=0&&x+k<W;k++){ int i=y-k; int j=x+k; if(S[i][j]!='G'){ v.pb(0); continue; } int a=0; if(j>0&&j+1<W&&S[i][j-1]=='R'&&S[i][j+1]=='W')a++; if(i>0&&i+1<H&&S[i-1][j]=='R'&&S[i+1][j]=='W')a+=2; v.pb(a); } memset(dp,0,sizeof(dp)); for(int i=0;i<v.size();i++){ rep(j,2){ rep(k,2){ int tmp=dp[i][j]; if((v[i]>>k&1)&&j==k)tmp++; chmax(dp[i+1][k],tmp); } } } return max(dp[v.size()][0],dp[v.size()][1]); } signed main(){ cin>>H>>W; rep(i,H)cin>>S[i]; int ans=0; for(int i=0;i<H;i++)ans+=solve(i,0); for(int i=1;i<W;i++)ans+=solve(H-1,i); cout<<ans<<endl; return 0; }
4問目 COMMUTER_PASS
これ3問目と位置が逆では
適切に最短S-Tパスを選んで、「Uから、パス上の頂点のどれか までの最短コスト」+「Vから、(略」を最小化したい。
まず、S,T,U,Vからdijkstraする。
次に、S-Tパスのうち、「Uから到達すべき場所」が「Vから到達すべき場所」よりS側にある場合について、dpする。(頂点を、Sからの最短距離によって順序づけると、最短経路DAG(元のグラフから、最短S-Tパスに使われる可能性がある辺のみを残したグラフ)みたいなやつに沿ってdpできる)
順序が逆の場合も同じようにできて、おわり
予想難易度:7
#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=1001001001001001001ll; int N,M; vector<pint>G[111111]; vint dijkstra(int s){ vint dist(N,INF); dist[s]=0; priority_queue<pint,vector<pint>,greater<pint>>que; que.push({0,s}); while(que.size()){ int c,v; tie(c,v)=que.top(); que.pop(); if(dist[v]<c)continue; for(auto &e:G[v]){ if(dist[e.fi]<=c+e.se)continue; dist[e.fi]=c+e.se; que.push({dist[e.fi],e.fi}); } } return dist; } int dp[222222]; signed main(){ cin>>N>>M; int S,T,U,V; cin>>S>>T>>U>>V;S--;T--;U--;V--; rep(i,M){ int a,b,c; cin>>a>>b>>c; a--;b--; G[a].pb({b,c}); G[b].pb({a,c}); } vint distS=dijkstra(S); vint distT=dijkstra(T); vint distU=dijkstra(U); vint distV=dijkstra(V); vpint ord; rep(i,N)ord.pb({distS[i],i}); sort(all(ord)); int ans=INF; fill_n(dp,N,INF); rep(t,N){ int v=ord[t].se; chmin(dp[v],distU[v]); chmin(ans,dp[v]+distV[v]); for(auto &e:G[v]){ if(distS[v]+e.se+distT[e.fi]!=distS[T])continue; chmin(dp[e.fi],dp[v]); } } fill_n(dp,N,INF); rep(t,N){ int v=ord[t].se; chmin(dp[v],distV[v]); chmin(ans,dp[v]+distU[v]); for(auto &e:G[v]){ if(distS[v]+e.se+distT[e.fi]!=distS[T])continue; chmin(dp[e.fi],dp[v]); } } cout<<ans<<endl; return 0; }
5問目 SNAKE_ESCAPING
なんか非想定っぽいやりかたで強引に通してしまった(半分全列挙みたいなノリで適当に)
無理かなあと思ったけど処理を出来るだけbit演算とかで簡潔にしていったら通った(最近のコンピュータすごい)
#include<bits/stdc++.h> using namespace std; #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 X=12; int L; int Q; int S[1<<20]; char buf[1<<22]; int table[1<<12]; vpint lis[81*81*81]; int ans[1111111]; void solve(int l,int r,int e,int d){ if(d==X){ rep(i,lis[e].size()){ int d=lis[e][i].fi; int &a=ans[lis[e][i].se]; for(int j=0;j<1<<(L-X);j++){ /* bool ok=true; rep(k,L-X){ int tmp=d>>(2*k)&3; if(tmp==2)continue; if((j>>k&1)!=tmp)ok=false; } if(ok)a+=S[l+j]; */ if(!(table[j]&d))a+=S[l+j]; } } return; } solve(l,(l+r)/2,e*3,d+1); solve((l+r)/2,r,e*3+1,d+1); rep(i,(r-l)/2)S[l+i]+=S[l+i+(r-l)/2]; solve(l,(l+r)/2,e*3+2,d+1); rep(i,(r-l)/2)S[l+i]-=S[l+i+(r-l)/2]; } signed main(){ scanf("%d%d",&L,&Q); scanf("%s",buf); rep(i,1<<L)S[i]=buf[i]-'0'; chmin(X,L); rep(i,1<<(L-X)){ for(int j=L-X-1;j>=0;j--){ table[i]<<=2; if(i>>j&1)table[i]+=2; else table[i]++; } } rep(i,Q){ scanf("%s",buf); int e=0; rep(j,X){ e*=3; if(buf[j]=='?')e+=2; else if(buf[j]=='1')e++; } int d=0; for(int j=X;j<L;j++){ d<<=2; if(buf[j]=='0')d+=2; else if(buf[j]=='1')d++; } lis[e].pb({d,i}); } solve(0,1<<L,0,0); rep(i,Q)printf("%d\n",ans[i]); return 0; }
おわりに
初めて全完出来た(まあめちゃくちゃ易化していましたが)
予選のときも思ったけど、ボス問がJOIらしくないですね
