ARC053 D: 2 つの山札

こういう後から合流して重複しうるものをうまく重複しないような汎用的テクとして、1ステップ進むときに追加する文字が同じなのに到達先が違う、というケースがないように、同じ文字で複数通りの結果に分岐するときはそれらを集合として状態に持っておく、というものがある。

多分このDPでもちゃんと遷移順とかしっかりやって普通のDPテーブルに押し込むことは可能で、そうするとO(N^2)になるんだろうけど、ややこしいのでサボった。

見た感じもっと実装が楽な解があるっぽいけど、発想を無にする戦略でいくならこっちの方が楽。

#include<stdio.h>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
int p[1100];
int q[1100];
long long mod=1000000007;
struct state{
	short t[4];
	state(){for(int i=0;i<4;i++)t[i]=-1;}
};
inline bool operator<(const state &a,const state &b){
	for(int i=0;i<4;i++)if(a.t[i]!=b.t[i])return a.t[i]<b.t[i];
	return false;
}
int pn[1100];
int qn[1100];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){scanf("%d",p+i);p[i]--;}
	for(int i=0;i<a;i++){scanf("%d",q+i);q[i]--;}
	reverse(p,p+a);
	reverse(q,q+a);
	for(int i=0;i<a;i++)pn[i]=qn[i]=-1;
	for(int i=a-1;i>0;i--){
		pn[p[i-1]]=p[i];
		qn[q[i-1]]=q[i];
	}
	queue<state>Q;
	map<state,int>dp;
	state st;
	st.t[0]=p[0];
	st.t[1]=q[0];
	Q.push(st);
	dp[st]=1;
		
	while(Q.size()){
		state now=Q.front();
		Q.pop();
		int tmp=dp[now];
	//	printf("%d %d %d %d: %d\n",now.t[0],now.t[1],now.t[2],now.t[3],tmp);
		for(int i=0;i<4;i++){
			if(now.t[i]==-1)continue;
			bool ok=true;
			for(int j=0;j<i;j++)if(now.t[i]==now.t[j])ok=false;
			if(!ok)continue;
			state to;
			int ind=0;
			for(int j=0;j<4;j++){
				if(now.t[j]==now.t[i]){
					int ad;
					if(j%2==0)ad=qn[now.t[j^1]];
					else ad=pn[now.t[j^1]];
				//	printf("%d %d\n",now.t[j^1],ad);
					if(ad!=-1){
						to.t[ind+j%2]=now.t[j];
						to.t[ind+!(j%2)]=ad;
						ind+=2;
					}
				}
			}
		//	printf("%d %d %d %d\n",to.t[0],to.t[1],to.t[2],to.t[3]);
			if(to.t[0]<to.t[2]){
				swap(to.t[0],to.t[2]);
				swap(to.t[1],to.t[3]);
			}
			if(to.t[0]==to.t[2]&&to.t[1]==to.t[3]){
				to.t[2]=to.t[3]=-1;
			}
			if(dp.count(to))dp[to]=(dp[to]+tmp)%mod;
			else{
				dp[to]=tmp;
				Q.push(to);
			}
		}
		if(~pn[now.t[0]]||~qn[now.t[1]])dp.erase(now);
	}
	state go;
	go.t[0]=p[a-1];
	go.t[1]=q[a-1];
	printf("%d\n",dp[go]);
}