AOJ 2288 Oh, My Goat!

今思えば意外にすんなり解いたもののアイデアは力作っぽいので、別記事にした。

H Oh, My Goat!

全力で怪しい解法をしたが、まあ辺数的にも状態数少なそうなのでどうとでもなりそうだったし予想を大きく裏切り一瞬で通った。

まあ基本方針として、与えられる2つのグラフをA,Bと名づけると、

  • f(Aで今いる地点番号,Bで今いる地点番号,Aでできてるstring,Bでできてるstring)

でmap使ってメモ化再帰

  • そんで、AでできてるstringとBでできてるstringで先頭で一致している部分はもう削除していいので、少し考えると、片方が空文字列にならなきゃいけないことが分かる。
  • たとえば"ABC"と"AB"ってのがあったら"C"と""が残る。もし空が残らなかったらそれは一致しない文字列になる。状態のための情報保持としては必要な感じのものだけ残ってうれしい。
  • 適当にやると問題点が出てきて、再帰関数の中でどっちか進むようにしていると、『先にAのほうで1進んでBのほうで1進む』ってのと、『先にBのほうで1進んでAのほうで1進む』ってのが重複することが分かる。
  • これの改善方法は簡単で、Aの番号がBの番号より大きいもしくはAでもう動くとこないならBの方で動く。逆が成り立つならAのほうで動くためそれも実行みたいな感じ。

変なソースなのですごく汚い。

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;
 
int n[2],m[2];
map< pair<string,string> , int > memo[501][501];
vector< vector<int> > a[2];
vector< vector<string> > b[2];
 
//グラフAでの番号p1 , グラフBでの番号p2 , グラフAで今できている文字列s1 , グラフBで今できている文字列s2
int dfs(int p1,int p2,string s1,string s2){
		// 終着のときの処理。s1とs2が一致している(⇔ s1=s2=""なら1返すそれ以外なら0。
		if(p1 == n[0]-1 && p2 == n[1]-1) return (s1 == "" && s2 == "");
		
		// メモ化
		if(memo[p1][p2].count(make_pair(s1,s2))) return memo[p1][p2][make_pair(s1,s2)];

		
		int ans = 0;
		
		// p1<=p2かつ、Aで動けるなら、Aで動く。それ以外ならBで動く。
		if(p1 <= p2 || p2 == n[1]-1){
			for(int i = 0 ; i < a[0][p1].size() ; i++){
					//とりあえずxとyに対し、次のs1,s2候補として文字列つくる。
					string x = s1 + b[0][p1][i];
					string y = s2;
					int I = 0 , J = 0;
					//一致部分を数える。
					for( ; I < x.size() && J < y.size() && x[I] == y[J] ; ) I++ , J++ ;
					
					//どっちかが空なら今まで一致しているということだから続行。
					if( I == x.size() || J == y.size() ){
							
							//まあここは消しているだけ
							if( I == x.size() && I == y.size() ) x = "" , y = "";
							else if( I == x.size() ) x = "" , y = y.substr(J);
							else if( J == y.size() ) x = x.substr(I) , y = "";
								
							//本質はここ
							ans = ( ans + dfs(a[0][p1][i],p2,x,y) ) % 1000000007;
					}
			}
		}//ここelseにしてさぼるとWA
		if(p1 > p2 || p1 == n[0]-1){
			//上と同じ、Bで動いてるだけ
			for(int j = 0 ; j < a[1][p2].size() ; j++){
					string x = s1;
					string y = s2 + b[1][p2][j] ;
					int I = 0 , J = 0;
					for( ; I < x.size() && J < y.size() && x[I] == y[J] ; ) I++ , J++ ;
					if( I == x.size() || J == y.size() ){
							
							if( I == x.size() && I == y.size() ) x = "" , y = "";
							else if( I == x.size() ) x = "" , y = y.substr(J);
							else if( J == y.size() ) x = x.substr(I) , y = "";
							
							ans = ( ans + dfs(p1, a[1][p2][j],x,y) ) % 1000000007;
					}
			}
		}
		
		return memo[p1][p2][make_pair(s1,s2)] = ans;
}

int main(){
		int T;cin >> T;
		while(T--){
				for(int i = 0 ; i < 2 ; i++){
						cin >> n[i] >> m[i];
						//cout << n[i] << " " << m[i] << endl;
						a[i].clear(); b[i].clear(); a[i].resize((unsigned)n[i]) , b[i].resize((unsigned)n[i]);
						for(int j = 0 ; j < m[i] ; j++){
								int A,B; string C;
								cin >> A >> B >> C;
								a[i][A].push_back(B);
								b[i][A].push_back(C);
						}
				}
				for(int i = 0 ; i < 501 ; i++)
					for(int j = 0 ; j < 501 ; j++)
						memo[i][j].clear();
				cout << dfs(0,0,"","") << endl;
		}
}