JOI 予選
満点狙いで行ったけど多分バグって116点。
1:やる
#include<stdio.h> #include "stdafx.h" #include<algorithm> using namespace std; int main() { FILE *fr=fopen("2013-yo-t1-in5.txt","r"); FILE *fw=fopen("out5.txt","w"); int res,pa,pb,sa,sb; fscanf(fr,"%d%d%d%d%d",&res,&pa,&pb,&sa,&sb); fprintf(fw,"%d\n",res-max((pa+sa-1)/sa,(pb+sb-1)/sb)); }
2:やる
#include<stdio.h> #include "stdafx.h" #include<vector> #include<algorithm> using namespace std; int hai[3][101]; int main() { FILE *fr=fopen("2013-yo-t2-in5.txt","r"); FILE *fw=fopen("out5.txt","w"); int num; fscanf(fr,"%d",&num); vector<int>vec[3]; for(int i=0;i<num;i++) { int za,zb,zc; fscanf(fr,"%d%d%d",&za,&zb,&zc); hai[0][za]++; hai[1][zb]++; hai[2][zc]++; vec[0].push_back(za); vec[1].push_back(zb); vec[2].push_back(zc); } for(int i=0;i<num;i++) { int sum=0; for(int j=0;j<3;j++) { if(hai[j][vec[j][i]]<=1) { sum+=vec[j][i]; } } fprintf(fw,"%d\n",sum); } }
3:やる。ファイルからのcinが分からないのでつくった。
#include<stdio.h> #include "stdafx.h" #include<vector> #include<algorithm> #include<string> using namespace std; FILE *fr; FILE *fw; string rea() { string ret; for(;;) { char zan; fscanf(fr,"%c",&zan); if(zan=='\n') { break; } ret.push_back(zan); } return ret; } int main() { fr=fopen("2013-yo-t3-in5.txt","r"); fw=fopen("out5.txt","w"); int num; char gomi; fscanf(fr,"%d%c",&num,&gomi); string mok=rea(); int ret=0; for(int i=0;i<num;i++) { string zan=rea(); bool han=false; for(int j=0;j<zan.size();j++) { for(int k=1;k<zan.size();k++) { if(j+k*(mok.size()-1)>=zan.size()) { break; } bool jud=true; for(int l=0;l<mok.size();l++) { if(mok[l]!=zan[j+k*l]) { jud=false; } } if(jud) { han=true; } } } if(han) { ret++; } } fprintf(fw,"%d\n",ret); }
4:DP。
#include<stdio.h> #include "stdafx.h" #include<vector> #include<algorithm> #include<math.h> #include<stdlib.h> using namespace std; typedef pair<int,int>pii; typedef pair<int,pii>pi3; int dp[200][200]; int main() { FILE *fr=fopen("2013-yo-t4-in5.txt","r"); FILE *fw=fopen("out5.txt","w"); int num,clo; fscanf(fr,"%d%d",&num,&clo); vector<int>tem; for(int i=0;i<num;i++) { int zan; fscanf(fr,"%d",&zan); tem.push_back(zan); } vector<pi3>vec; for(int i=0;i<clo;i++) { int za,zb,zc; fscanf(fr,"%d%d%d",&za,&zb,&zc); vec.push_back(make_pair(zc,make_pair(za,zb))); } for(int i=0;i<200;i++) { for(int j=0;j<200;j++) { dp[i][j]=-1000000000; } } for(int i=0;i<clo;i++) { if(vec[i].second.first<=tem[0]&&tem[0]<=vec[i].second.second) { dp[0][i]=0; } } for(int i=1;i<num;i++) { for(int j=0;j<clo;j++) { if(vec[j].second.first<=tem[i]&&tem[i]<=vec[j].second.second) { for(int k=0;k<clo;k++) { dp[i][j]=max(dp[i][j],dp[i-1][k]+abs(vec[k].first-vec[j].first)); } } } } int maxi=0; for(int i=0;i<clo;i++) { maxi=max(maxi,dp[num-1][i]); } fprintf(fw,"%d\n",maxi); }
5:座圧。予選で座圧出るとはびっくり。いもす法したくなるけど予選なのでしなくてもよい。
#include<stdio.h> #include "stdafx.h" #include<vector> #include<algorithm> #define mp(A,B) make_pair(A,B) #define mq(A,B,C,D) mp(mp(A,B),mp(C,D)) #define ms(A,B,C,D,E,F) mp(mp(A,B),mq(C,D,E,F)) using namespace std; typedef long long ll; typedef pair<ll,ll>pii; typedef pair<pii,pii>pi4; typedef pair<pii,pi4>pi6; vector<ll>uni(vector<ll>vec) { vector<ll>ret; ll now=-1; for(int i=0;i<vec.size();i++) { if(now!=vec[i]) { ret.push_back(vec[i]); now=vec[i]; } } return ret; } int map[100][100][100]; int main() { FILE *fr=fopen("2013-yo-t5-in5.txt","r"); FILE *fw=fopen("out5.txt","w"); int num,gen; fscanf(fr,"%d%d",&num,&gen); vector<pi6>vec; vector<ll>sx,sy,sd; for(int i=0;i<num;i++) { ll za,zb,zc,zd,ze,zf; fscanf(fr,"%lld%lld%lld%lld%lld%lld",&za,&zb,&zc,&zd,&ze,&zf); vec.push_back(ms(za,zd,zb,ze,zc,zf)); sx.push_back(za); sx.push_back(zd); sy.push_back(zb); sy.push_back(ze); sd.push_back(zc); sd.push_back(zf); } sort(sx.begin(),sx.end()); sort(sy.begin(),sy.end()); sort(sd.begin(),sd.end()); sx=uni(sx); sy=uni(sy); sd=uni(sd); for(int i=0;i<num;i++) { int low1=lower_bound(sx.begin(),sx.end(),vec[i].first.first)-sx.begin(); int low2=lower_bound(sx.begin(),sx.end(),vec[i].first.second)-sx.begin(); int low3=lower_bound(sy.begin(),sy.end(),vec[i].second.first.first)-sy.begin(); int low4=lower_bound(sy.begin(),sy.end(),vec[i].second.first.second)-sy.begin(); int low5=lower_bound(sd.begin(),sd.end(),vec[i].second.second.first)-sd.begin(); int low6=lower_bound(sd.begin(),sd.end(),vec[i].second.second.second)-sd.begin(); for(int j=low1;j<low2;j++) { for(int k=low3;k<low4;k++) { for(int l=low5;l<low6;l++) { map[j][k][l]++; } } } } ll ret=0; for(int i=0;i<sx.size()-1;i++) { for(int j=0;j<sy.size()-1;j++) { for(int k=0;k<sd.size()-1;k++) { if(map[i][j][k]>=gen) { ret+=(sx[i+1]-sx[i])*(sy[j+1]-sy[j])*(sd[k+1]-sd[k]); } } } } fprintf(fw,"%lld\n",ret); }
6:難しかった。DP。直前5回分くらいを覚えておくと解ける。(testcase1でバグって16点なはず)
ソースコードは検算用に6個前まで持ったのを上げてる。
#include<stdio.h> #include "stdafx.h" #include<vector> #include<algorithm> using namespace std; int dp[4][52][52][4096]; int map[53][53]; bool isused(int hash,int nx,int ny,int mx,int my) { int ps[6]; for(int q=0;q<6;q++) { ps[q]=hash%4; hash/=4; } bool han=false; for(int q=0;q<6;q++) { if(ps[q]==0) { nx++; } if(ps[q]==1) { ny++; } if(ps[q]==2) { nx--; } if(ps[q]==3) { ny--; } if(nx==mx&&ny==my) { return true; } } return false; } int main() { FILE *fr=fopen("2013-yo-t6-in5.txt","r"); FILE *fw=fopen("out5.txt","w"); int mx,my,gen; fscanf(fr,"%d%d%d",&mx,&my,&gen); for(int i=0;i<53;i++) { for(int j=0;j<53;j++) { map[i][j]=-1; } } for(int i=0;i<4;i++) { for(int j=0;j<52;j++) { for(int k=0;k<52;k++) { for(int l=0;l<4096;l++) { dp[i][j][k][l]=-1000000000; } } } } dp[0][1][1][4095]=0; for(int i=0;i<mx;i++) { for(int j=0;j<my;j++) { char zan; fscanf(fr," %c",&zan); if(zan=='.') { map[i][j]=0; } if('1'<=zan&&zan<='9') { map[i][j]=zan-'0'; } } } for(int k=0;k<=gen;k++) { for(int i=0;i<mx;i++) { for(int j=0;j<my;j++) { if(map[i][j]==-1) { continue; } for(int p=0;p<4096;p++) { int zp=p; p%=1024; if(isused(zp,i+1-1,j+1,i+1,j+1)) { dp[k][i+1][j+1][p*4+2]=max(dp[k][i+1][j+1][p*4+2],dp[k][i+1-1][j+1][zp]); } else { dp[k][i+1][j+1][p*4+2]=max(dp[k][i+1][j+1][p*4+2],dp[k][i+1-1][j+1][zp]+map[i][j]); } if(isused(zp,i+1,j+1-1,i+1,j+1)) { dp[k][i+1][j+1][p*4+3]=max(dp[k][i+1][j+1][p*4+3],dp[k][i+1][j+1-1][zp]); } else { dp[k][i+1][j+1][p*4+3]=max(dp[k][i+1][j+1][p*4+3],dp[k][i+1][j+1-1][zp]+map[i][j]); } if(k!=0) { if(!isused(zp,i+1+1,j+1,i+1,j+1)) { dp[k][i+1][j+1][p*4]=max(dp[k][i+1][j+1][p*4],dp[k-1][i+1+1][j+1][zp]+map[i][j]); } if(!isused(zp,i+1,j+1+1,i+1,j+1)) { dp[k][i+1][j+1][p*4+1]=max(dp[k][i+1][j+1][p*4+1],dp[k-1][i+1][j+1+1][zp]+map[i][j]); } } p=zp; } int m=0; for(int q=0;q<4096;q++) { m=max(m,dp[k][i+1][j+1][q]); } } } } int maxi=0; for(int i=0;i<=gen;i++) { for(int j=0;j<4096;j++) { maxi=max(maxi,dp[i][mx][my][j]); } } fprintf(fw,"%d\n",maxi); }
http://gyazo.com/f09b304d3e0f2ec7c6c163205153f74f
これはすくしょとったのをあとからgyazoってるので不正ではないです