Codeforces 105 C. Item World
問題
n個のアイテムがある。
それぞれ、名前、class,atk,def,res,sizeが定まっている。
classはweapon, armor, orbのいずれかである。
sizeは、アイテムに宿らせることのできる精霊の数である。
k個のアイテムに宿る精霊的な何かがある。
それぞれ、名前、type,bonusが定まっている。
typeはgladiator, sentry, physicianのいずれかである。
gladiatorはatkを、sentryはdefを、physicianはresをbonusだけ上昇させる。
精霊はアイテムからアイテムへ移動させることができる。
ただし、移動先のアイテムに空きがなければならず、精霊をアイテムの外に出したままにしたり、
消したりすることはできない。
今、精霊を適当に移し替えることにより一つのweaponのatkの値を最大化し、
atkの値がタイなら、一つのarmorのsentryのdefの値を最大化し、それもタイなら
orbのresの値を最大化したい。
そのような装備および精霊の組み合わせ方を出力せよ。
答えが複数ある場合どれを出力してもかまわない。
制約条件
n≦100
k≦1000
方針
クソ実装問。
ごりごり実装する。
ソースコード
見られたものじゃない。
struct R{ int bonus; string name,type; R(){} R(int b,string n,string t):bonus(b),name(n),type(t){} bool operator<(const R &r)const{ return bonus>r.bonus; } }; struct I{ int atk,def,res,size; string name,cls; I(){} I(int a,int d,int r,int s,string n,string c): atk(a),def(d),res(r),size(s),name(n),cls(c){} vector<R> rs; }; I item[100]; R resi[1000]; vector<R> gs,ss,ps; int n,k; void pv(int p){ cout<<item[p].name<<" "<<item[p].rs.size(); rep(i,item[p].rs.size())cout<<" "<<item[p].rs[i].name; cout<<endl; } void run(){ cin>>n; int sum=0; rep(i,n){ int a,d,r,s; string n,c; cin>>n>>c>>a>>d>>r>>s; item[i]=I(a,d,r,s,n,c); sum+=s; } cin>>k; rep(i,k){ int b; string nm,t,h; cin>>nm>>t>>b>>h; resi[i]=R(b,nm,t); rep(j,n)if(item[j].name==h)item[j].rs.pb(resi[i]); if(t[0]=='g')gs.pb(resi[i]); else if(t[0]=='s')ss.pb(resi[i]); else ps.pb(resi[i]); } if(sum==k){ int mxw,mxa,mxo; int w=-1,a=-1,o=-1; rep(i,n)if(item[i].cls[0]=='w'){ int s=item[i].atk; rep(j,item[i].rs.size())if(item[i].rs[j].type[0]=='g') s+=item[i].rs[j].bonus; if(s>w)w=s, mxw=i; } else if(item[i].cls[0]=='a'){ int s=item[i].def; rep(j,item[i].rs.size())if(item[i].rs[j].type[0]=='s') s+=item[i].rs[j].bonus; if(s>a)a=s, mxa=i; } else if(item[i].cls[0]=='o'){ int s=item[i].res; rep(j,item[i].rs.size())if(item[i].rs[j].type[0]=='p') s+=item[i].rs[j].bonus; if(s>o)o=s, mxo=i; } pv(mxw); pv(mxa); pv(mxo); return; } sort(all(gs)); sort(all(ss)); sort(all(ps)); //cerr<<gs.size()<<" "<<ss.size()<<" "<<ps.size()<<endl; rep(i,n)item[i].rs.clear(); int mxw,mxa,mxo,w=-1,a=-1,o=-1; rep(i,n)if(item[i].cls[0]=='w'){ int s=item[i].atk; rep(j,min(item[i].size,(int)gs.size()))s+=gs[j].bonus; if(s>w)w=s, mxw=i; } else if(item[i].cls[0]=='a'){ int s=item[i].def; rep(j,min(item[i].size,(int)ss.size()))s+=ss[j].bonus; if(s>a)a=s, mxa=i; } else if(item[i].cls[0]=='o'){ int s=item[i].res; rep(j,min(item[i].size,(int)ps.size()))s+=ps[j].bonus; if(s>o)o=s, mxo=i; } rep(i,min(item[mxw].size,(int)gs.size()))item[mxw].rs.pb(gs[i]); rep(i,min(item[mxa].size,(int)ss.size()))item[mxa].rs.pb(ss[i]); rep(i,min(item[mxo].size,(int)ps.size()))item[mxo].rs.pb(ps[i]); vector<R> v; for(int i=min(item[mxw].size,(int)gs.size());i<gs.size();i++)v.pb(gs[i]); for(int i=min(item[mxa].size,(int)ss.size());i<ss.size();i++)v.pb(ss[i]); for(int i=min(item[mxo].size,(int)ps.size());i<ps.size();i++)v.pb(ps[i]); int k=0; while(k<v.size()&&item[mxw].rs.size()<item[mxw].size)item[mxw].rs.pb(v[k++]); while(k<v.size()&&item[mxa].rs.size()<item[mxa].size)item[mxa].rs.pb(v[k++]); while(k<v.size()&&item[mxo].rs.size()<item[mxo].size)item[mxo].rs.pb(v[k++]); pv(mxw); pv(mxa); pv(mxo); }