TopCoder SRM 665 Div1 Medium HatParade

本番惜しいところまで行っていたけど最後まで詰め切れず。
http://community.topcoder.com/stat?c=problem_statement&pm=13965

問題

初期状態でN個の帽子が左右一列に並んでいる。
各帽子には正整数V[i]と正整数S[i]が書かれていた。

S[i]は以下のいずれかを満たすような数値であった。

• 自身のV[i]と、自身より左側にある帽子のV[i]の総和
• 自身のV[i]と、自身より右側にある帽子のV[i]の総和

ここでこれらの帽子をでたらめに並び替えた。
並び替えた後の各帽子のV[i]、S[i]が与えられる。
これらの帽子を再度並び替えたとき、V,Sの関係が上記条件を満たすような並び替え方は何通りあるか答えよ。

解法

V[i]全体の総和をTとする。
左端から帽子列を埋めていき、すでに置かれた帽子のV[i]の総和をUとすると、次にこの帽子列における帽子は以下の何れかである。

• S[i]の条件の前者を満たすもの。すなわちU+V[i]==S[i]となる帽子。
• S[i]の条件の後者を満たすもの。すなわちT-U==S[i]となる帽子。

あとは状態を(未配置の帽子,U)としてメモ化再帰で行えばよいが、これではTLEするケースがある。
例えば帽子を(V[i],S[i])とすると、左端２個と右端２個が以下のようになるケースがある。
(1,1) (2,3) (....) (1,3) (2,2)
この場合、(....)の部分が条件を満たす帽子列なら、先頭２つと末尾２つを入れ替えてもこの帽子列は条件を満たす。
上記の例だと、先に(1,1) (2,3)を置いた後残りの(....) (1,3) (2,2)をDFSするのと、先に(2,2) (1,3)を置いて残りの(....) (1,1) (2,3)を処理するのは未配置の帽子の内容が異なるので、メモ化の効果はなく再度DFSしなければならない。
このように(V[i],S[i])の値によっては倍々でDFSの実行回数が増える可能性がある。

そこで左端からだけ埋めるのをやめ、左端と右端から順次埋めていくことにする。
左端と右側のうちV[i]の和が小さい方に１個追加する、という処理を繰り返す。
そうするとDFSの過程で、上記の例を持ち出すなら
(1,1) (2,3) (....) (1,3) (2,2)
先に(1,1)(2,3)(1,3)(2,2)の位置が確定してから(....)の部分を処理するが、(1,1)(2,3)と(1,3)(2,2)はどちらが前でも、(....)の部分は同一なのでメモ化再帰で処理が増えるのを防止できる。

ll mo=1000000007;

class HatParade {
	public:
	int N;
	ll tsum;
	map<pair<vector<pair<ll,ll>>,ll>,ll> memo;
	
	ll dfs(vector<pair<ll,ll>> M,ll lsum,ll rsum) {
		if(M.empty()) return 1;
		if(lsum>rsum) swap(lsum,rsum);
		if(memo.count({M,lsum})) return memo[{M,lsum}];
		
		ll ret=0;
		int i;
		FOR(i,M.size()) {
			if((lsum+M[i].first==M[i].second) || (M[i].second==tsum-lsum)) {
				vector<pair<ll,ll>> M2=M;
				M2.erase(M2.begin()+i);
				ret += dfs(M2,lsum+M[i].first,rsum);
			}
		}
		return memo[{M,lsum}]=ret%mo;
	}
	
	int getPermutation(vector <int> value, vector <int> sum) {
		
		memo.clear();
		N=value.size();
		
		int i;
		tsum=0;
		vector<pair<ll,ll>> M;
		FOR(i,N) M.push_back({value[i],sum[i]}), tsum+=value[i];
		sort(M.begin(),M.end());
		
		return dfs(M,0,0);
	}
}

まとめ

なかなか面白い問題だった。
でも本番左端から埋めるだけのアプローチを取っていたので、バグを解決してもTLEしてたな…。