GCJ Round2
ABCともにgreedy要素が少しずつありました。実装軽いし問題面白かったです(小並感)
A: 凸関数なので端同士を結んで行ったほうがいい。stackでほげる
#include<stdio.h> #include "stdafx.h" #include<vector> #include<algorithm> #include<stack> using namespace std; typedef long long ll; typedef pair<ll,ll>pii; typedef pair<pii,ll>pi3; ll mod=1000002013; int main() { FILE *fr=fopen("a-large.in","r"); FILE *fw=fopen("out0.txt","w"); int data; fscanf(fr,"%d",&data); for(int p=0;p<data;p++) { ll cit,way; fscanf(fr,"%lld%lld",&cit,&way); vector<pi3>vec; ll ans=0; for(int i=0;i<way;i++) { ll za,zb,zc; fscanf(fr,"%lld%lld%lld",&za,&zb,&zc); ans+=(((2*cit+1-(zb-za))*(zb-za)/2)%mod)*zc; ans%=mod; vec.push_back(make_pair(make_pair(za,0),zc)); vec.push_back(make_pair(make_pair(zb,1),zc)); } ll ret=0; sort(vec.begin(),vec.end()); stack<pii>st; for(int i=0;i<vec.size();i++) { if(vec[i].first.second==0) { st.push(make_pair(vec[i].first.first,vec[i].second)); } else { ll now=vec[i].second; for(;;) { pii zan=st.top(); if(zan.second<now) { ret+=(((2*cit+1-(vec[i].first.first-zan.first))*(vec[i].first.first-zan.first)/2)%mod)*zan.second; ret%=mod; now-=zan.second; st.pop(); } else { ret+=(((2*cit+1-(vec[i].first.first-zan.first))*(vec[i].first.first-zan.first)/2)%mod)*now; ret%=mod; st.top().second-=now; break; } } } } fprintf(fw,"Case #%d: %lld\n",p+1,(ans+mod-ret)%mod); } }
B:にぶたん。勝てるところまで目先の利益にこだわって勝ち続ける
#include<stdio.h> #include "stdafx.h" #include<vector> #include<algorithm> using namespace std; typedef long long ll; ll minord(ll num,ll per) { ll ans=num; ll low=num-per-1; for(;;) { if(low==0) { return ans; } low=(low-1)/2; ans/=2; } } ll maxord(ll num,ll per) { ll ans=num; ll low=per; for(;;) { if(low==0) { return num+1-ans; } low=(low-1)/2; ans/=2; } } int main() { FILE *fr=fopen("b-large.in","r"); FILE *fw=fopen("out0.txt","w"); int data; fscanf(fr,"%d",&data); for(int p=0;p<data;p++) { ll num,pri; fscanf(fr,"%lld%lld",&num,&pri); num=(1LL<<num); ll beg1=0,end1=num-1; for(;;) { ll med=(beg1+end1)/2+1; //printf("%lld %lld %lld %lld\n",beg1,end1,med,maxord(num,med)); if(maxord(num,med)>pri) { end1=med-1; } else { beg1=med; } if(beg1==end1) { break; } } ll beg2=0,end2=num-1; for(;;) { ll med=(beg2+end2)/2+1; if(minord(num,med)>pri) { end2=med-1; } else { beg2=med; } if(beg2==end2) { break; } } fprintf(fw,"Case #%d: %lld %lld\n",p+1,beg1,beg2); } }
C:大小関係すべてに辺を張る。項に対して「それより前にあってlisの値がそれより大きいもの」に全部辺を張って「それより前にあってlisの値がその項より1だけ小さいものの中で最後のもの」に逆向きの辺を張るだけで解ける。ldsも同様
#include<stdio.h> #include "stdafx.h" #include<vector> #include<algorithm> using namespace std; bool pat[2000][2000]; int ans[2000]; int ine[2000]; bool flag[2000]; int main() { FILE *fr=fopen("c-large.in","r"); FILE *fw=fopen("out0.txt","w"); int data; fscanf(fr,"%d",&data); for(int p=0;p<data;p++) { int num; fscanf(fr,"%d",&num); for(int i=0;i<2000;i++) { for(int j=0;j<2000;j++) { pat[i][j]=false; } ans[i]=-1; ine[i]=0; flag[i]=false; } vector<int>lis,lds; for(int i=0;i<num;i++) { int zan; fscanf(fr,"%d",&zan); lis.push_back(zan); } for(int i=0;i<num;i++) { int zan; fscanf(fr,"%d",&zan); lds.push_back(zan); } for(int i=0;i<num;i++) { for(int j=0;j<i;j++) { if(lis[j]>=lis[i]) { pat[i][j]=true; } } for(int j=i-1;j>=0;j--) { if(lis[j]+1==lis[i]) { pat[j][i]=true; break; } } } for(int i=num-1;i>=0;i--) { for(int j=num-1;j>i;j--) { if(lds[j]>=lds[i]) { pat[i][j]=true; } } for(int j=i+1;j<num;j++) { if(lds[j]+1==lds[i]) { pat[j][i]=true; break; } } } for(int i=0;i<num;i++) { for(int j=0;j<num;j++) { if(pat[i][j]) { ine[j]++; } } } int pt=1; for(int i=0;i<num;i++) {/* for(int j=0;j<num;j++) { printf("%d ",ine[j]); } printf("\n");*/ for(int j=0;j<num;j++) { if(ine[j]==0&&(!flag[j])) { for(int k=0;k<num;k++) { if(pat[j][k]) { ine[k]--; } } ans[j]=pt++; flag[j]=true; break; } } } fprintf(fw,"Case #%d: ",p+1); for(int i=0;i<num;i++) { if(i!=0) { fprintf(fw," "); } fprintf(fw,"%d",ans[i]); } fprintf(fw,"\n"); } }
別にABCはそこまで難しいと思わなかったしすらすら進めてたら20位になってた。なぜこれで20位なのかわからないけど取り合えずとてもいい順位だったので喜ぶことにします