TopCoder SRM 637 Div1 Easy GreaterGame

SRM637に参加。
Easyの問題解釈を間違ってしまいタイムロス。
案の定Mediumを解けずレート微増で終了。
http://community.topcoder.com/stat?c=problem_statement&pm=13504

問題

1～2Nの数値が１枚ずつの計2N枚のカードを用いて２人でゲームをする。
互いに自分の持ちカードの順番を定めたのち、１枚ずつ出して数値の大きい方が勝って１ポイント得られるというシンプルなゲームである。

自分の手持ちのカードhard[i]と相手のカードの出す順番sothe[i]が与えられる。
ただし相手のカードの順番は一部不明である。

自分が最適手を取る場合、得られるポイントの期待値を答えよ。

解法

まず順番がわかっているカードに対してはこちらの出すカードが一意に決まる。
相手のカードのうち順番が判明している分を数値で昇順に並べ、以下のように処理する。

• 相手のカードに勝てるカードがあれば、そのうち最小の番号のカードを出し１ポイント確実に得る
• 相手のカードに勝てるカードがなければ、手持ちの最小の番号のカードを処理しておく

後は相手のカードの順番が不明な何枚かが残る。
相手のカード順はランダムなので、こちらも残りの全カードを等確率で出した場合のポイント期待値を求めればよい。

class GreaterGame {
	public:
	double calc(vector <int> hand, vector <int> sothe) {
		int N=hand.size();
		double w=0;
		int i,j,vis[101];
		vector<int> H,S,S2;
		ZERO(vis);
		
		FOR(i,N) vis[hand[i]]=1;
		FOR(i,N) if(sothe[i]!=-1) vis[sothe[i]]=1,S.push_back(sothe[i]);
		for(i=1;i<=2*N;i++) if(vis[i]==0) S2.push_back(i);
		H=hand;
		sort(H.begin(),H.end());
		sort(S.begin(),S.end());
		
		FOR(i,S.size()) {
			int ok=0;
			FOR(j,H.size()) if(H[j]>S[i]) {
				w+=1;
				ok=1;
				H.erase(H.begin()+j);
				break;
			}
			if(ok==0) H.erase(H.begin());
		}
		FOR(i,H.size()) FOR(j,S2.size()) if(H[i]>S2[j]) w += 1.0/H.size();
		
		return w;
	}
}

まとめ

順番判明済みのカードに対して最適手を取るの、何となく思いついたけど大丈夫で助かった。