kmjp's blog

競技プログラミング参加記です

TopCoder SRM 544 Div2 Hard AliceBobShuffle

これもさほど難しくないかな?
http://community.topcoder.com/stat?c=problem_statement&pm=11865

問題

AliceとBobが数字の書かれたカードの山を持っている。

2人がカードの上から順に全部のカードを共有の山に重ねていく。(重ねる順番は1枚ずつ交互でなくてもよい)
また、全部重ね終わったら、また2人が共有の山から自分の山にカードを移していく。(こちらも順番は交互でなくても良い)

AliceとBobの初期のカードの山と、完了後のカードの山が与えられたとき、そのような山を構築できる処理手順の組み合わせを答えよ。

解法

1回共有の山に入れると考えるとややこしいが、最初のAliceまたはBobの山から最後のAliceとBobの山に直接カードを放り込むと考えよう。
状態として[Aliceの初期山残り枚数][Bobの初期山残り枚数][Aliceの完了後山枚数][Bobの完了後山枚数]と4つが考えられるが、全カード枚数はわかっているので3つわかれば残り1つもわかる。

よって以下のコードでは状態を[Aliceの初期山残り枚数][Bobの初期山残り枚数][Aliceの完了後山枚数]で持ち、AliceまたはBobの初期山の一番上のカードを、AliceまたはBobの完了後山に放り込める(数字が一致する)かどうかで判定してDPすればよい。
O(N^3)なので時間は余裕。

ll dp[51][51][51];
ll mo=1000000007;
class AliceBobShuffle {
	public:
	int countWays(vector <int> AS, vector <int> BS, vector <int> AE, vector <int> BE) {
		int i,asi,bsi,aei,bei;
		map<int,int> nc;
		ITR(it,AS) nc[*it]++;
		ITR(it,BS) nc[*it]++;
		ITR(it,AE) nc[*it]--;
		ITR(it,BE) nc[*it]--;
		ITR(it,nc) if(it->second) return 0;
		ZERO(dp);
		int asl=AS.size(),bsl=BS.size();
		int ael=AE.size(),bel=BE.size(),nn=asl+bsl;
		
		dp[asl][bsl][0]=1;
		for(asi=asl;asi>=0;asi--) for(bsi=bsl;bsi>=0;bsi--) {
			for(aei=0;aei<=ael;aei++) {
				bei = nn-asi-bsi-aei;
				if(bei<0 || bei>bel) continue;
				if(dp[asi][bsi][aei]==0) continue;
				if(asi>0 && aei<ael && AS[asi-1]==AE[ael-1-aei]) 
					dp[asi-1][bsi][aei+1] = (dp[asi-1][bsi][aei+1] + dp[asi][bsi][aei]) % mo;
				if(bsi>0 && aei<ael && BS[bsi-1]==AE[ael-1-aei]) 
					dp[asi][bsi-1][aei+1] = (dp[asi][bsi-1][aei+1] + dp[asi][bsi][aei]) % mo;
				if(asi>0 && bei<bel && AS[asi-1]==BE[bel-1-bei]) 
					dp[asi-1][bsi][aei] = (dp[asi-1][bsi][aei] + dp[asi][bsi][aei]) % mo;
				if(bsi>0 && bei<bel && BS[bsi-1]==BE[bel-1-bei]) 
					dp[asi][bsi-1][aei] = (dp[asi][bsi-1][aei] + dp[asi][bsi][aei]) % mo;
			}
		}
		
		return dp[0][0][ael];
	}
};

*まとめ