TopCoderOpen 2017 Round1C Hard EllysRPS

出てたらWAしてました。
https://community.topcoder.com/stat?c=problem_statement&pm=14580

問題

N人の相手とK回ずつじゃんけんを行う。
全員の手の順番はわかっているものとする。

全員に対し同じ順番で同じ手を出すものとするとき、全員と勝ち負け数がタイになるような手順は何通りあるか。

解法

半分全列挙で解く。
前後半それぞれDFS等で手順を総当たりして勝ち負けの差分を求め、前後半で勝ち負け数が正負逆になるものを掛け合わせよう。

以下のコードは一回手順を作り切ってから全員の勝ち負け数を求めているので1.7sと結構重い。
DFSで勝ち負け数を更新しながら手を列挙していけばもう少し速いはず。

class EllysRPS {
	public:
	int N,L;
	vector<string> SS[11];
	map<vector<int>,ll> hoge(vector <string> S,int L,int R) {
		char win[256];
		win['R']='P';
		win['P']='S';
		win['S']='R';
		
		int i,j;
		map<vector<int>,ll> ret;
		FORR(s,SS[R-L]) {
			vector<int> V(N,0);
			FOR(i,N) for(j=L;j<R;j++) {
				if(win[s[j-L]]==S[i][j]) V[i]++;
				else if(s[j-L]!=S[i][j]) V[i]--;
			}
			ret[V]++;
		}
		
		return ret;
	}
	
	long long getCount(vector <string> S) {
		N=S.size();
		L=S[0].size();
		
		int i,j;
		SS[0].clear();
		SS[0].push_back("");
		FOR(i,10) {
			SS[i+1].clear();
			FORR(s,SS[i]) {
				SS[i+1].push_back(s+"R");
				SS[i+1].push_back(s+"P");
				SS[i+1].push_back(s+"S");
			}
		}
		
		map<vector<int>,ll> A=hoge(S,0,L/2);
		map<vector<int>,ll> B=hoge(S,L/2,L);
		
		ll ret=0;
		FORR(r,A) {
			auto r2=r.first;
			FORR(e,r2) e=-e;
			ret += r.second*B[r2];
		}
		
		return ret;
		
	}
}

まとめ

DFSした方が速いのに一旦列挙する癖は止めた方がよさそう。