joi2016予選
よせんでました。とてもたのしかったです。
1問目
適当にやる。やるだけ。
#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() typedef vector<int>vint; typedef pair<int,int>pint; int get(int n){ vint v(n); rep(i,n)cin>>v[i]; sort(v.rbegin(),v.rend()); return accumulate(v.begin(),v.begin()+n-1,0); } signed main(){ int a=get(4); int b=get(2); cout<<a+b<<endl; return 0; }
2問目
バトンのやつ。やるだけ。
#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() typedef vector<int>vint; typedef pair<int,int>pint; int N,M; int a[100]; signed main(){ cin>>N>>M; rep(i,N)cin>>a[i]; for(int k=1;k<=M;k++){ rep(i,N-1){ if(a[i]%k>a[i+1]%k)swap(a[i],a[i+1]); } } rep(i,N)cout<<a[i]<<endl; return 0; }
3問目
ロシアの旗のやつ。全探索。
#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() typedef vector<int>vint; typedef pair<int,int>pint; int H,W; int a[50][50]; signed main(){ cin>>H>>W; rep(i,H)rep(j,W){ char c; cin>>c; if(c=='W')a[i][j]=0; else if(c=='B')a[i][j]=1; else a[i][j]=2; } int ans=114514; for(int i=1;i<H-1;i++){ for(int j=i+1;j<H;j++){ int cnt=0; for(int y=0;y<i;y++)rep(x,W)if(a[y][x]!=0)cnt++; for(int y=i;y<j;y++)rep(x,W)if(a[y][x]!=1)cnt++; for(int y=j;y<H;y++)rep(x,W)if(a[y][x]!=2)cnt++; ans=min(ans,cnt); } } cout<<ans<<endl; return 0; }
4問目
散歩のやつ。つらら的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() typedef vector<int>vint; typedef pair<int,int>pint; const int SIZE=100000; int N,T,Q; int A[SIZE],D[SIZE]; int dp[SIZE]; signed main(){ cin>>N>>T>>Q; rep(i,N)cin>>A[i]>>D[i]; rep(i,N){ if(D[i]!=2)continue; if(i==0)dp[i]=A[i]-T; else if(D[i-1]==1)dp[i]=max(A[i]-T,A[i]-(A[i]-A[i-1])/2); else dp[i]=max(A[i]-T,dp[i-1]); } for(int i=N-1;i>=0;i--){ if(D[i]!=1)continue; if(i==N-1)dp[i]=A[i]+T; else if(D[i+1]==2)dp[i]=min(A[i]+T,A[i]+(A[i+1]-A[i])/2); else dp[i]=min(A[i]+T,dp[i+1]); } while(Q--){ int x;cin>>x;x--; cout<<dp[x]<<endl; } return 0; }
5問目
ゾンビのやつ。タクシーみたいに幅やってdijkstraやる。
#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() typedef vector<int>vint; typedef pair<int,int>pint; const int SIZE=100000; const int INF=1001001001001001001LL; struct edge{ int to,cost; edge(int to,int cost):to(to),cost(cost){} }; int N,M,K,S; int P,Q; int C[SIZE]; vector<edge>G[SIZE]; int dist[SIZE]; void bfs(){ fill_n(dist,N,INF); queue<int>que; rep(i,K){ dist[C[i]]=0; que.push(C[i]); } while(que.size()){ int v=que.front();que.pop(); rep(i,G[v].size()){ int to=G[v][i].to; if(dist[to]<=dist[v]+1)continue; dist[to]=dist[v]+1; que.push(to); } } } void build(){ rep(i,N){ vector<edge>vec; rep(j,G[i].size()){ int to=G[i][j].to; if(dist[to]==0)continue; if(to==N-1)vec.pb(edge(to,0)); else if(dist[to]<=S)vec.pb(edge(to,Q)); else vec.pb(edge(to,P)); } G[i]=vec; } } void dijkstra(){ fill_n(dist,N,INF); dist[0]=0; priority_queue<pint,vector<pint>,greater<pint> >que; que.push(pint(0,0)); while(que.size()){ pint p=que.top();que.pop(); if(dist[p.second]<p.first)continue; rep(i,G[p.second].size()){ edge &e=G[p.second][i]; if(dist[e.to]<=p.first+e.cost)continue; dist[e.to]=p.first+e.cost; que.push(pint(dist[e.to],e.to)); } } } signed main(){ cin>>N>>M>>K>>S; cin>>P>>Q; rep(i,K)cin>>C[i],C[i]--; rep(i,M){ int a,b;cin>>a>>b;a--;b--; G[a].pb(edge(b,1)); G[b].pb(edge(a,1)); } bfs(); build(); dijkstra(); cout<<dist[N-1]<<endl; return 0; }
6問目
お菓子買うやつ。お土産みたいなbitDPを気合で書く。
#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() typedef vector<int>vint; typedef pair<int,int>pint; const int dy[]={0,-1,0,1}; const int dx[]={-1,0,1,0}; int H,W; int a[1000][1000]; int memo[1000][1000][1<<4]; int dfs(int y,int x,int s){ if(~memo[y][x][s])return memo[y][x][s]; if(y+1==H&&x+1==W)return 0; int ret=1145141919; int lis[4]={0},sum=0; rep(i,4){ int ny=y+dy[i],nx=x+dx[i]; if(ny<0||ny>=H||nx<0||nx>=W||!a[ny][nx])continue; if(i==0&&(s>>1&1))continue; if(i==1&&(s>>2&1))continue; lis[i]=a[ny][nx]; sum+=lis[i]; } if(y+1!=H){ if(sum==0){ ret=min(ret,dfs(y+1,x,(s&1)*2+4)); } else if(sum==lis[3]){ ret=min(ret,dfs(y+1,x,(s&1)*2+4)+sum); } else{ if(lis[0]){ ret=min(ret,dfs(y+1,x,(s&1)*2+12)+sum-lis[0]); } if(lis[1]){ ret=min(ret,dfs(y+1,x,(s&1)*2+12)+sum-lis[1]); } if(lis[2]){ ret=min(ret,dfs(y+1,x,(s&1)*2+4)+sum-lis[2]); } } } if(x+1!=W){ if(sum==0){ ret=min(ret,dfs(y,x+1,(s>>3&1)*4+2)); } else if(sum==lis[2]){ ret=min(ret,dfs(y,x+1,(s>>3&1)*4+2)+sum); } else{ if(lis[0]){ ret=min(ret,dfs(y,x+1,(s>>3&1)*4+3)+sum-lis[0]); } if(lis[1]){ ret=min(ret,dfs(y,x+1,(s>>3&1)*4+3)+sum-lis[1]); } if(lis[3]){ ret=min(ret,dfs(y,x+1,(s>>3&1)*4+2)+sum-lis[3]); } } } return memo[y][x][s]=ret; } signed main(){ scanf("%d%d",&H,&W); rep(i,H)rep(j,W){ char c;scanf(" %c",&c); if(isdigit(c))a[i][j]=c-'0'; } memset(memo,-1,sizeof(memo)); printf("%d\n",dfs(0,0,0)); return 0; }
まとめ
たのしかった。
