TopCoder SRM 826 : Div1 Easy Div2 Hard TwoFairDice

悪くない出来ではあるんだけど、今回もミスが多い。
https://community.topcoder.com/stat?c=problem_statement&pm=17477

問題

2人がそれぞれ6面ダイスを持っている。
それぞれ自身のダイスを転がし、目が大きい方が勝ちというゲームを考える。

1人目のダイスの目はすべて確定している。
2人目のダイスは一部の目が未確定なので、0～1000のいずれかを埋めたい。
両者の勝率が等しくなるような目の埋め方は何通りか。

解法

以下のいずれでも解ける。

• 0～1000を座標圧縮したうえで、6重ループを回し未確定の目の値を総当たりする
• 状態として、確定済みの目における勝ちパターン数の差ごとに目の組み合わせの総数を持ち、DPする。

以下は前者だけど、後者の方が解きやすそうね。

class TwoFairDice {
	public:
	long long finish(vector <int> A, vector <int> B) {
		sort(ALL(A));
		vector<int> V;
		V.push_back(0);
		FORR(a,A) {
			V.push_back(a);
			V.push_back(a+1);
		}
		V.push_back(1001);
		sort(ALL(V));
		V.erase(unique(ALL(V)),V.end());
		FORR(a,A) a=lower_bound(ALL(V),a)-V.begin();
		int M=V.size()-1;
		FORR(a,B) {
			a=lower_bound(ALL(V),a+1)-V.begin()-1;
		}
		ll ret=0;
		int C[6]={};
		FOR(C[0],M) FOR(C[1],M) FOR(C[2],M) FOR(C[3],M) FOR(C[4],M) FOR(C[5],M) {
			int i;
			ll pat=1;
			FOR(i,6) {
				if(i<B.size()) {
					if(C[i]!=B[i]) break;
				}
				else {
					pat*=V[C[i]+1]-V[C[i]];
				}
			}
			if(i<6) continue;
			int win=0;
			int x,y;
			FOR(x,6) FOR(y,6) {
				if(A[x]>C[y]) win++;
				if(A[x]<C[y]) win--;
			}
			if(win==0) {
				ret+=pat;
			}
		}
		return ret;
		
		
	}
}

まとめ

なんか方針ミスでタイムロスすることが多いな。