SRM 400〜420埋め
くけけけけ
400 ReversalChain
問題概要
0,1からなる文字列がある。
i文字目からj文字目までを入れ替える操作をr(i,j)と書く。
r(i1,j1)、r(i2,j2)、...、r(in,jn)のような操作の列が、
i1≦i2≦...≦inかつj1≧j2≧...≧jnを満たすとき、この操作の列をreversal chainと呼ぶ。
initの文字列をgoalの文字列にするようなreversal chainのうち、最小の長さのものの長さを求めよ。
制約条件
init,goalの長さ≦50
initとgoalの長さは等しい。
解法
長さが20なら典型的なビットDP...
操作は文字列を反転させるだけというより強い条件があることでもっと効率的な解法があるのだろうか。
という訳でEditorial見た。
dp[i][j][k][l]に長さiの、initのjから始まる文字列とgoalの長さkから始まる文字列を対応させるのにかかる反転の数とする。ただしl=1のときは、initのその部分文字列は反転している。
すると、
initの長さiの文字列(a...b)とgoalの(c...d)を対応させるとき、
a=cの場合、dp[i][j][k]05|AllCyclelength[0]=dp[i-1][j+1][k+1][0]
a=dの場合、dp[i][j][k][0]=dp[i-1][j+1][k][1]+1...というように漸化式が立つのでDPできる。
dpのkeyを文字列そのままにする解法もあるらしい。
ソースコード
int min(int a,int b,int c,int d){ return min(min(a,b),min(c,d)); } int dp[60][60][60][2]; class ReversalChain { public: int minReversal(string init, string goal) { //from editorial int n=init.size(); rep(i,n)rep(j,n)rep(k,2)dp[1][i][j][k]=init[i]==goal[j]?0:inf; for(int x=2;x<=n;x++)rep(a,n-x+1)rep(b,n-x+1) { dp[x][a][b][0]=min ( init[a]==goal[b] ? dp[x-1][a+1][b+1][0]:inf, init[a+x-1]==goal[b+x-1] ? dp[x-1][a][b][0]:inf, init[a]==goal[b+x-1] ? dp[x-1][a+1][b][1]+1:inf, init[a+x-1]==goal[b] ? dp[x-1][a][b+1][1]+1:inf ); dp[x][a][b][1]=min ( init[a]==goal[b] ? dp[x-1][a+1][b+1][0]+1:inf, init[a+x-1]==goal[b+x-1] ? dp[x-1][a][b][0]+1:inf, init[a]==goal[b+x-1] ? dp[x-1][a+1][b][1]:inf, init[a+x-1]==goal[b] ? dp[x-1][a][b+1][1]:inf ); } return dp[n][0][0][0]==inf?-1:dp[n][0][0][0]; } };
404 KSubstring
問題概要
解法
誤答
ll getnear(set<ll> &near,ll v){
set<ll>::iterator it=lower_bound(all(near),v);
if(it==near.end())return *(--it);
ll a=*it,b;
if(it==near.begin())return a;
b=*(--it);
if(abs(v-a)<abs(v-b))return a;
return b;
}
class KSubstring {
public:
vector <int> maxSubstring(int A0, int X, int Y, int M, int n) {
int a[3000];
a[0]=A0;
rep(i,n-1)a[i+1]=(ll(a[i])*X+Y)%M;
ll val=1ll<<60; int mxk=-1;
for(int k=n/2;k>0;k--){
ll s1=0,s2=0;
set<ll> s;
rep(i,k)s1+=a[i], s2+=a[k+i];
s.insert(s1);
ll near=getnear(s,s2);
if(abs(s2-near)<val)val=abs(s2-near), mxk=k;
for(int i=0;i<n-2*k;i++){
s1+=a[k+i]-a[i];
s2+=a[2*k+i]-a[k+i];
s.insert(s1);
ll near=getnear(s,s2);
if(abs(s2-near)<val)val=abs(s2-near), mxk=k;
}
}
vi ans;
ans.pb(mxk); ans.pb((int)val);
return ans;
}
};
誤答2
class KSubstring { public: vector <int> maxSubstring(int A0, int X, int Y, int M, int n) { ll a[3000],sum[3001]={}; a[0]=sum[1]=A0; rep(i,n-1)a[i+1]=(a[i]*X+Y)%M, sum[i+2]=sum[i+1]+a[i+1]; ll val=1ll<<60; int mxi=-1; for(int len=1;len<=n;len++){ vector<pair<ll,int> > ary; rep(i,n-len+1)ary.pb(mp(sum[i+len]-sum[i],i));05|AllCyclelength sort(all(ary)); rep(i,n-len)for(int j=i+1;j<=n-len&&ary[j].first-ary[i].first==ary[i+1].first-ary[i].first;j++){ ll d=ary[j].first-ary[i].first; int l=ary[i].second, r=ary[j].second, k; if(l>r)swap(l,r); if(l+len-1<r)k=len; else k=r-l; if(d<val||d==val&&k>mxi)val=d, mxi=k; } } vi ans; ans.pb(mxi); ans.pb((int)val); return ans; } };
405 AllCyclelength
問題概要
有向グラフの接続行列が与えられる。
スタートおよびゴールの頂点s,tが与えられるとき、長さkのパスでsを始点としtを終点とするようなものが存在するかをあらわす文字列を、次のように表示せよ。
0001011101101(10)
↑循環しない部分 ↑その先は10で永遠に循環
方針
循環しない部分の長さはそんなに長くならないので、実際に最初の2000くらいまで文字列を書き出して（このくらいまで書き出さないとダメというのがわかるのに5回くらいSystemTest落とした）、循環する部分を見つけて圧縮するのがよいらしい。
循環しない部分が長くならないのがなぜかはよくわからず。
循環節の長さは最大でも頂点数の50で抑えられるので、循環節の候補2500通り総当たりすればよい。
int n; bool e[30][30],f[30][30],g[30][30]; void mul(){ rep(i,n)rep(j,n)g[i][j]=e[i][j], e[i][j]=0; rep(i,n)rep(j,n){ rep(k,n)e[i][j]|=f[i][k]&&g[k][j]; } } class AllCycleLengths { public: string findAll(vector <string> arcs) { n=arcs.size(); rep(i,n)rep(j,n)e[i][j]=f[i][j]=arcs[i][j]=='Y'; string s; rep(i,1500){ int ok=0; rep(i,n)ok|=e[i][i]; s.pb('0'+ok); mul(); } for(int len=1;len<50;len++){ string ptnloop,ptn,bestptn; int bestpos=inf; rep(i,len){ ptn=ptnloop=s.substr(1000+i,len); while(ptnloop.size()<200)ptnloop+=ptn; int pos; if((pos=s.find(ptnloop))==string::npos)continue; if(bestpos>pos)bestpos=pos,bestptn=ptn; } if(bestpos==inf)continue; s=s.substr(0,bestpos)+"("+bestptn+")"; return s; } return ""; } };
418 StampsCollection
問題概要
n（≦50)個のスタンプを持っている。（それぞれの番号は0〜n-1）
m人の人が欲しがるスタンプのリスト、および、それを買う値段が与えられる。
- それぞれの人が欲しがるスタンプは最大2つ
- １つのスタンプを欲しがる人は最大二人
- スタンプを欲しがる人が二つのスタンプを欲しがっている場合、セットじゃないと買わない
このとき、最大の利益を求めよ。
方針
グラフの次数は最大2
なのでループする部分とループしない部分にわけられる。
それぞれでDP.
以下の2点がコードを簡潔に書くポイント
- グラフを 値段[人Aが欲しがるスタンプの番号1][2]とする。
- まずは次数が1の点から（dfsして頂点のリストを作って）DP
- 次にループだけが残るので、またDPする。 このとき開始位置を最初とその次と見て、線状の時と同じようにやるだけでよい。
ソースコード
int n, deg[50], p[50][50]; bool v[50]; vi u; void rec(int c){ if(v[c])return; u.pb(c); v[c]=1; rep(i,n)if(i!=c&&p[c][i]>0)rec(i); } int calc(){ int m=u.size(), dp[51]={}; rep(i,m){ dp[i+1]=max(dp[i+1],dp[i]+p[u[i]][u[i]]); if(i+1<m)dp[i+2]=max(dp[i+2],dp[i]+p[u[i]][u[i+1]]); } return dp[m]; } class StampsCollection { public: int sell(int n, vector <string> demand, vector <int> price) { ::n=n; rep(i,n)rep(j,n)p[i][j]=0; rep(i,demand.size()){ int a,b; sscanf((demand[i]+" -1").c_str(),"%d%d",&a,&b); if(b<0)b=a; p[a][b]=p[b][a]=max(p[a][b],price[i]); } rep(i,n)rep(j,n)if(i!=j&&p[i][j]>0)deg[i]++; rep(i,n)v[i]=0; int ans=0; rep(i,2)rep(j,n)if(!v[j]&&(i||deg[j]==1)){ u.clear(); rec(j); int ret=calc(); u.pb(u[0]); u.erase(u.begin()); ret=max(ret,calc()); ans+=ret; } return ans; } };
401 ParticleCollision
問題概要
二つの軌跡(cos(pi*t),sin(pi*t),t), (vx*t+x0,vy*t+y0,vz*t+z0)が、
一点で交わるならその座標を、
二点以上で交わるなら(0,0,0)を、
交わらないなら空のvectorを返せ。
方針
(vx*t+x0)^2+(vy*t+y0)^2 = 1として二次方程式を立てて場合わけ。
軌跡が交わるというのを、「二点が衝突する」と読み違えててかなりハマる。
ソースコード
class ParticleCollision { public: vector <double> collision(int vx, int vy, int vz, int x0, int y0, int z0) { double a=vx*vx+vy*vy, b=2*(vx*x0+vy*y0), c=x0*x0+y0*y0-1; vector<double> ans; if(a==0){ if(c==0){ if(vz!=0){ rep(i,3)ans.pb(0); return ans; } else{ if(abs(x0-cos(PI*z0))<EPS){ ans.pb(x0); ans.pb(y0); ans.pb(z0); } return ans; } } else return ans; } double D=b*b-4*a*c; if(D<-EPS)return ans; if(D<EPS){ double t=-b/(2*a), T=vz*t+z0; if(abs(cos(PI*T)-(vx*t+x0))>EPS)return ans; ans.pb(vx*t+x0); ans.pb(vy*t+y0); ans.pb(vz*t+z0); return ans; } double t1=(-b+sqrt(D))/(2*a), T1=vz*t1+z0; double t2=(-b-sqrt(D))/(2*a), T2=vz*t2+z0; if(abs(cos(PI*T1)-(vx*t1+x0))>EPS&&abs(cos(PI*T2)-(vx*t2+x0))>EPS)return ans; if(abs(cos(PI*T1)-(vx*t1+x0))<EPS&&abs(cos(PI*T2)-(vx*t2+x0))<EPS){ rep(i,3)ans.pb(0); return ans; } if(abs(cos(PI*T1)-(vx*t1+x0))<EPS){ ans.pb(vx*t1+x0); ans.pb(vy*t1+y0); ans.pb(vz*t1+z0); return ans; } else{ ans.pb(vx*t2+x0); ans.pb(vy*t2+y0); ans.pb(vz*t2+z0); } return ans; } };
