SRM637 Div1 Easy - GreaterGame

問題

SnukeとSotheがカードをn枚ずつ、合計2n枚持っていて、各カードには1〜2nの数字が重複なしで書かれている
この状態からnターンのゲームをする
各ターンではお互いにカードを1枚同時に出し、数字がより大きいカードを出した方が1点得る
Sotheがiターン目に出すカードの情報を数ターン分知っている時にSnukeが理想的に動いて得られる得点の期待値を求める

解法

1) iターン目にSotheがkを出すとわかっている場合
k+1以上のカードを持っているならそのうち最小値を出して勝つのが一番得で、
k+1以上のカードを持っていないならどうせ何を出しても負けるから手札の最小値を出して負けるのが一番得

2) iターン目にSotheが出すカードがわからない場合
そのようなターンがqターンあるとする
Sotheは最初のSnukeの手札と1)で出てこなかった数字q個をランダムに出すことになる
Snukeが1)で残った手札q枚のうちどれか(=aとする)を出した時に勝つ確率は (Sotheのq枚のうちa-1以下のカードの枚数) / q
これがそのまま「Sotheが何を出すかわからないターンにSnukeがaを出した時の得点の期待値」だからこれを各aについて足し合わせればok

実装

出てきた数字をbool sで管理して最終的にfalseになってるもの==Sotheがいつ出すかわからないカードをbbに入れてる
あと何となく実装楽になるような気がしたから二分探索してるけどあんま良いことなかった

class GreaterGame {
	public:
	double calc(vector<int> a, vector<int> b) {
		int n = a.size();
		sort(a.begin(), a.end());
		bool s[111] = {};
		rep(i,n) s[a[i]] = 1;
		int q = 0;
		double res = 0;
		rep(i,n) {
			if (b[i]==-1) q++;
			else {
				s[b[i]] = 1;
				auto t = upper_bound(a.begin(), a.end(), b[i]);
				if (t==a.end()) a.erase(a.begin());
				else a.erase(t), res += 1;
			}
		}
		vector<int> bb;
		reps(i,1,2*n+1) if (!s[i]) bb.push_back(i);
		each(i,a) {
			auto t = upper_bound(bb.begin(), bb.end(), i);
			res += 1. * (t - bb.begin()) / q;
		}
		return res;
	}
};