Hardはどうせ2-SATなので解いてもここに載せる気が起きない。
250：危険なアレ
Medium openなので難しいということを事前にわかって開けた。難しいと分かっているのでゆっくりやれた。2通りに場合わけするだけ。
// I like wolves!! #include <vector> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <sstream> #include <iostream> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <queue> #include <string.h> #include <complex> using namespace std; class PeriodicJumping { public: int minimalTime(int x, vector <int> a) { int n=a.size(); x=abs(x); long long L=x; long long R=x; long long D=0; if(x==0)return 0; for(int i=0;i<n;i++){ D+=a[i]; if(R-a[i]>=0)L=max(0LL,L-a[i]); else L=-(R-a[i]); R+=a[i]; if(L==0)return i+1; } if(D<x){ int ret=n*(x/D); x%=D; long long t=0; for(int i=0;i<n;i++){ if(x<=t)break; ret++; t+=a[i]; } return ret; } for(int i=0;i<n;i++){ if(R-a[i]>=0)L=max(0LL,L-a[i]); else L=-(R-a[i]); if(L==0)return n+i+1; } return -1; } };
600：木 木
根を決める。各頂点から根までたどって条件ふやす→最小カット
600が解けたのは相当久しぶりだと思う。
// I like wolves!! #include <vector> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <sstream> #include <iostream> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <queue> #include <string.h> #include <complex> using namespace std; const int D_MAX_V=1000; const int D_v_size=1000; struct D_wolf{ int t,c,r; D_wolf(){t=c=r=0;} D_wolf(int t1,int c1,int r1){ t=t1;c=c1;r=r1; } }; vector<D_wolf>D_G[D_MAX_V]; int D_level[D_MAX_V]; int D_iter[D_MAX_V]; void add_edge(int from,int to,int cap){ D_G[from].push_back(D_wolf(to,cap,D_G[to].size())); D_G[to].push_back(D_wolf(from,0,D_G[from].size()-1)); } void D_bfs(int s){ for(int i=0;i<D_v_size;i++)D_level[i]=-1; queue<int> Q; D_level[s]=0; Q.push(s); while(Q.size()){ int v=Q.front(); Q.pop(); for(int i=0;i<D_G[v].size();i++){ if(D_G[v][i].c>0&&D_level[D_G[v][i].t]<0){ D_level[D_G[v][i].t]=D_level[v]+1; Q.push(D_G[v][i].t); } } } } int D_dfs(int v,int t,int f){ if(v==t)return f; for(;D_iter[v]<D_G[v].size();D_iter[v]++){ int i=D_iter[v]; if(D_G[v][i].c>0&&D_level[v]<D_level[D_G[v][i].t]){ int d=D_dfs(D_G[v][i].t,t,min(f,D_G[v][i].c)); if(d>0){ D_G[v][i].c-=d; D_G[D_G[v][i].t][D_G[v][i].r].c+=d; return d; } } } return 0; } int max_flow(int s,int t){ int flow=0; for(;;){ D_bfs(s); if(D_level[t]<0)return flow; for(int i=0;i<D_v_size;i++)D_iter[i]=0; int f; while((f=D_dfs(s,t,99999999))>0){flow+=f;} } return 0; } class DoubleTree { public: vector<int>ga[60]; vector<int>gb[60]; int reva[60]; int revb[60]; int use[60][60]; void dfsa(int a,int b){ for(int i=0;i<ga[a].size();i++){ if(ga[a][i]==b)continue; reva[ga[a][i]]=(a); dfsa(ga[a][i],a); } } void dfsb(int a,int b){ for(int i=0;i<gb[a].size();i++){ if(gb[a][i]==b)continue; revb[gb[a][i]]=(a); dfsb(gb[a][i],a); } } int maximalScore(vector <int> a, vector <int> b, vector <int> c, vector <int> d, vector <int> score) { int n=a.size()+1; int ret=0; int INF=99999999; int val=0; for(int i=0;i<n-1;i++){ ga[a[i]].push_back(b[i]); ga[b[i]].push_back(a[i]); gb[c[i]].push_back(d[i]); gb[d[i]].push_back(c[i]); } for(int i=0;i<n;i++)if(score[i]>0)val+=score[i]; for(int i=0;i<n;i++){ for(int j=0;j<1000;j++){ D_G[j].clear(); D_iter[j]=D_level[j]=0; } for(int j=0;j<n;j++)for(int k=0;k<n;k++)use[j][k]=0; // for(int j=0;j<n;j++)for(int k=0;k<n;k++) int s=n*2; int t=n*2+1; for(int j=0;j<n;j++){ add_edge(s,j,max(0,score[j])); add_edge(j,j+n,INF); add_edge(j+n,t,max(0,-score[j])); } for(int j=0;j<n;j++){ reva[j]=revb[j]=0; } dfsa(i,-1); dfsb(i,-1); // for(int j=0;j<n;j++)printf("%d: %d\n",j,reva[j]); // for(int j=0;j<n;j++)printf("%d: %d\n",j,revb[j]); for(int j=0;j<n;j++){ int at=j; while(at!=i){ at=reva[at]; use[j][at]=1; } } for(int j=0;j<n;j++){ int at=j; while(at!=i){ at=revb[at]; use[j][at]=1; } } for(int j=0;j<n;j++)for(int k=0;k<n;k++)if(use[j][k])add_edge(j+n,k,INF); ret=max(ret,val-max_flow(s,t)); } return ret; } };
1000：SAT SAT
2-SATでmin(a,b)=eってどう式にするんだろうね～という気分になった
Challenge:
どうせたくさん落ちるんだろうけど問題が問題なのでコードがみな汚くて読めない。無理。
2236 -> 2366 (+130)
ようやく相応レーティングになってきた。
