4日間で100問Div1Medium解くとか言ってしまいましたが、どう考えても無謀だったのでゆっくりMedium解いています。
SRM502 Div1Med(500)
解法：ソートしてDPをする。ソート基準を考える。
久しぶりにこういう問題を見たのでかかる時間だけでソートしてしまい反省。
わざわざ狙ってオーバーフローさせにかかるあたりVasylは悪質だと思う。
#include<algorithm> #include<vector> using namespace std; struct wolf{ int B; int C; int D; }; inline bool operator<(const wolf &a,const wolf &b){ return (long long)a.C*b.D>(long long)b.C*a.D; } class TheProgrammingContestDivOne{ public: long long dp[51][100001]; wolf v[50]; int find(int a,vector<int>b,vector<int>c,vector<int>d){ int n=b.size(); for(int i=0;i<n;i++){ v[i].B=b[i]; v[i].C=c[i]; v[i].D=d[i]; } std::sort(v,v+n); for(int i=0;i<n;i++){ for(int j=0;j<=a;j++){ dp[i+1][j]=max(dp[i][j],dp[i+1][j]); if(j+v[i].D<=a){ dp[i+1][j+v[i].D]=max(dp[i+1][j+v[i].D],dp[i][j]+v[i].B-(long long)v[i].C*(j+v[i].D)); } } } long long ret=0; for(int i=0;i<=n;i++) for(int j=0;j<=a;j++)ret=max(ret,dp[i][j]); return ret; } };
MSRM503 Div1Med(500)
解法：各村別々に考えて、それぞれどの頂点につながるかを確率求める。重要なのは何番目に距離が近いかだけ。
なかなか不安になる解法だけど、TopCoderらしいと思います。
import java.util.*; public class KingdomXCitiesandVillages{ public double determineLength(int []ax,int[]ay,int[]bx,int[]by){ int m=ax.length; int n=bx.length; double ret=0; for(int i=0;i<n;i++){ double Min=99999999; for(int j=0;j<m;j++){ Min=Math.min(Math.sqrt((double)(ax[j]-bx[i])*(ax[j]-bx[i])+(double)(ay[j]-by[i])*(ay[j]-by[i])),Min); } double c[]=new double[n-1]; int I=0; for(int j=0;j<n;j++){ if(i!=j){ c[I++]=Math.min(Min,Math.sqrt((double)(bx[j]-bx[i])*(bx[j]-bx[i])+(double)(by[j]-by[i])*(by[j]-by[i]))); } } Arrays.sort(c); double now=1; for(int j=0;j<n-1;j++){ ret+=c[j]/(j+1)/(j+2); now-=1.0/(j+1)/(j+2); } ret+=now*Min; } return ret; } }
SRM504 Div1Med(500)
解法：上から忠実に処理する。2の累乗or0が答えになる。
DPかと思ったらぜんぜんDPじゃなかった。
public class AlgridTwo{ public int makeProgram(String[]a){ int m=a.length; int n=a[0].length(); int MOD=1000000007; int ret=1; for(int i=0;i<m-1;i++){ int []dat=new int[n]; for(int j=0;j<n;j++){ dat[j]=-1; } for(int j=0;j<n-1;j++){ if(a[i].charAt(j)=='B'&&a[i].charAt(j+1)=='W'){ dat[j]=1; dat[j+1]=1; } if(a[i].charAt(j)=='W'&&a[i].charAt(j+1)=='B'){ dat[j]=0; dat[j+1]=0; } if(a[i].charAt(j)=='B'&&a[i].charAt(j+1)=='B'){ int c=dat[j]; dat[j]=dat[j+1]; dat[j+1]=c; } } boolean ok=true; int count=0; for(int j=0;j<n;j++){ if(dat[j]==1&&a[i+1].charAt(j)=='W')ok=false; if(dat[j]==0&&a[i+1].charAt(j)=='B')ok=false; if(dat[j]!=-1)count++; } if(!ok)return 0; for(int j=0;j<count;j++)ret=(ret+ret)%MOD; } return ret; } }
MSRM505 Div1Med(500)
(解法：O(√n)くらいになるように上手く処理する？)
大変そう。本番でも40人しか解いてない。
SRM506 Div1Med(600)
解法：車を割り当てるのでフロー
こういう割り当てはどういう風に流せばいいのか(max flow? min cost flow?)迷ってた。フローは練習不足な気がする。
フロー慣れている人なら600というほど難しくなさそうだけど、アルゴリズム自体が難しいので600なのは仕方ないかもしれない。
#include <vector> #include <algorithm> #include <iostream> #include <queue> #include <cstdio> #include<string> using namespace std; typedef int Weight; const Weight INF=99999999; struct Edge{ int dst,cap;Weight cost,rev; }; typedef vector<Edge> Node; typedef vector<Node> Graph; //srcからdstへ向かう容量cap,コストcostの辺をグラフに追加する void add_edge(Graph &G,int src,int dst,Weight cap,Weight cost){ G[src].push_back((Edge){dst,cap,cost,G[dst].size()}); G[dst].push_back((Edge){src,0,-cost,G[src].size()-1}); } //sからtへの流量fの最小費用流を求める //流せない場合は-1を返す int min_cost_flow(Graph &G,int s,int t,int f){ typedef pair<int,int> P; int res=0; int V=G.size(); vector<Weight> h(V,0); vector<int> prevv(V); vector<int> preve(V); while(f>0){ priority_queue<P,vector<P>,greater<P> > que; vector<Weight> dist(V,INF); dist[s]=0; que.push(P(0,s)); while(!que.empty()){ P p=que.top();que.pop(); int v=p.second; if(dist[v]<p.first)continue; for(int i=0;i<(int)G[v].size();i++){ Edge &e=G[v][i]; if(e.cap>0&&dist[e.dst]>dist[v]+e.cost+h[v]-h[e.dst]){ dist[e.dst]=dist[v]+e.cost+h[v]-h[e.dst]; prevv[e.dst]=v; preve[e.dst]=i; que.push(P(dist[e.dst],e.dst)); } } } if(dist[t]==INF){ return -1; } for(int v=0;v<V;v++)h[v]+=dist[v]; int d=f; for(int v=t;v!=s;v=prevv[v]){ d=min(d,G[prevv[v]][preve[v]].cap); } f-=d; res+=d*h[t]; for(int v=t;v!=s;v=prevv[v]){ Edge &e=G[prevv[v]][preve[v]]; e.cap-=d; G[v][e.rev].cap+=d; } } return res; } class SlimeXGrandSlimeAuto{ public: int g[50][50]; int travel(vector<int>a,vector<int>b,vector<string>c,int d,int e){ int n=c.size(); for(int i=0;i<n;i++)for(int j=0;j<n;j++)g[i][j]=99999999; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if('0'<=c[i][j]&&c[i][j]<='9')g[i][j]=c[i][j]-'0'+1; if('a'<=c[i][j]&&c[i][j]<='z')g[i][j]=c[i][j]-'a'+11; if('A'<=c[i][j]&&c[i][j]<='Z')g[i][j]=c[i][j]-'A'+37; } g[i][i]=0; } for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)g[i][j]=min(g[i][j],g[i][k]+g[k][j]); Graph wolf(2+b.size()+a.size()); int at=0; for(int i=0;i<b.size();i++){ add_edge(wolf,0,2+i,1,0); for(int j=0;j<a.size();j++){ add_edge(wolf,2+i,2+b.size()+j,1,g[at][a[j]]*d+g[a[j]][b[i]]*e); } add_edge(wolf,2+i,1,1,g[at][b[i]]*d); at=b[i]; } for(int i=0;i<a.size();i++)add_edge(wolf,2+b.size()+i,1,1,0); return min_cost_flow(wolf,0,1,b.size()); } };
Div1Med Solved
22 -> 26 (+4)
