TopCoder SRM 629 Div1 Medium CandyCollection

しょうもないミス…。
http://community.topcoder.com/stat?c=problem_statement&pm=13339

問題

幾つかの飴がある。これらの飴はN種類の形状とN種類の味を持つ。
各形状の飴はちょうど２種類の味があり、各味の飴はちょうど２種類の形状がある。

ここで、N個の店がある。
i番目の店はi番目の形状の飴を売っており、Type1[i]の味をNum1[i]個、Type2[i]の味をNum2[i]個撃っている。
同じ形状の飴は買ってみないと味がわからない。

確実に全種類の味の飴を１個以上手に入れるには、最少何個の飴を買う必要があるか。

解法

同じ味の飴を売っている店同士を辺でつなぐと、店同士はいくつかのループ関係になる。
後は個々のループにおいてDPしていけばよい。

ある店において各飴の買い方は以下のいずれかである。

• Type1[i]もType2[i]も不要なら、１個も買う必要はない。
• Type1[i]を確実に手に入れるには、Num2[i]+1個買えばType1[i]が1個は手に入る。
• Type2[i]を確実に手に入れるには、Num1[i]+1個買えばType2[i]が1個は手に入る。
• Type1[i]とType2[i]を両方確実に手に入れるには、max(Num1[i],Num2[i])+1個買えば両方1個は手に入る。

ループ内の店同士において、店iと店jはType2[i]==Type1[j]である場合に店jは店iの次である、とする。
店iでType2[i]を手に入れていれば、店jでType1[i]を買う必要はないし、その逆もしかり。
よって店iでType2[i]を買ったかどうか、で状態を持ってDPすればよい。
ただし注意として、店同士はループ状になっているので、それとは別に最初の店でType1を買ったかどうかも覚えておく。
すなわち状態として[最初の店でType1を買ったか][直前の店でType2を買ったか]の4通りを更新していけばよい。

int rev[1000];
int vis[1000];
int dpdp[1001][4];

class CandyCollection {
	public:
	int N;
	vector <int> T1,T2,N1,N2;
	int next(int type) {
		int i,j=0;
		FOR(i,N) if(vis[i]==0 && T1[i]==type) return i;
		FOR(i,N) if(vis[i]==0 && T2[i]==type) {
			swap(T1[i],T2[i]);
			swap(N1[i],N2[i]);
			return i;
		}
		return -1;
	}
	
	int solve(vector <int> Type1, vector <int> Number1, vector <int> Type2, vector <int> Number2) {
		N=Type1.size();
		MINUS(rev);
		int i,j,k;
		T1=Type1,T2=Type2;
		N1=Number1,N2=Number2;
		
		int tot=0;
		ZERO(vis);
		FOR(i,N) if(vis[i]==0) {
			FOR(j,N) FOR(k,4) dpdp[j][k]=10000000;
			dpdp[0][0]=0;
			dpdp[0][1]=N1[i]+1;
			dpdp[0][2]=N2[i]+1;
			dpdp[0][3]=max(N1[i],N2[i])+1;
			vis[i]=1;
			int cur=next(T2[i]);
			
			for(j=1;j<=N+1;j++) {
				vis[cur]=1;
				int tar=next(T2[cur]);
				if(tar==-1) {
					int x=min(dpdp[j-1][3],dpdp[j-1][2]+N2[cur]+1);
					x=min(x,dpdp[j-1][0]+max(N1[cur],N2[cur])+1);
					x=min(x,dpdp[j-1][1]+N1[cur]+1);
					tot+=x;
					break;
				}
				else {
					dpdp[j][0]=min(dpdp[j-1][1],dpdp[j-1][0]+N2[cur]+1);
					dpdp[j][1]=min(dpdp[j-1][1]+N1[cur]+1,dpdp[j-1][0]+max(N1[cur],N2[cur])+1);
					dpdp[j][2]=min(dpdp[j-1][3],dpdp[j-1][2]+N2[cur]+1);
					dpdp[j][3]=min(dpdp[j-1][3]+N1[cur]+1,dpdp[j-1][2]+max(N1[cur],N2[cur])+1);
				}
				cur=tar;
			}
		}
		return tot;
		
	}
}

まとめ

本番一部Num1とNum2を間違えて落とした。