AOJ 1184: Generic Poker

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1184

evimaさんのコードを見ながら解いたので完全に理解しているか怪しいが、おそらく日本語の解説が存在しないので書く。
というかもう一回やりたいのでその時用のメモ

間違ってる可能性が高いので間違ってたら教えて下さい

基本的なアイディア

すべてのパターンの手札を生成して、パターンに合致しているならば加算していく。
最後にすべてのパターン数で割ってやれば確率が出る。

手札のパターン生成について

手札はsortedなので、以下の様なコードにすることができる。

vector<int> hands;
void gen(int n){
	if(n==L){
		if(check())ans += count();
		return;
	}
	for(int i=hands[n-1];i<M;i++){
		hands[n]=i;
		gen(n+1);
	}
}

当然だがこれでは時間がかかりすぎるので、いくつか工夫をしてやる必要がある。

数字は高々7種類までしか使われないので、そこをどうにか減らしたい。

問題設定上、ランクの間に間隔がある時はいくつ離れていても問題ないことが読み取れるので、
sortedな手札の場合、隣り合うカードは
①同じ
②一個違い
③間隔がある
の3通りと考えて良い。

そうすると

vector<int> hands;
void gen(int n){
	if(n==L){
		if(check())ans += count();
		return;
	}
	hands[n] = hands[n-1];
	gen(n+1);
	hands[n] = hands[n-1]+1;
	gen(n+1);
	hands[n] = hands[n-1]+2;
	gen(n+1);
}

で十分だということがわかる。

パターンマッチ

上記の生成によって、パターンマッチには十分な情報を持つ手札が生成できている。
例えば手札は

1 1 2 4 4

のようになっている

①a b cの数字が決まっているとすると
それぞれのランクのカードが最低限何枚必要かがわかる（*はあまりを適当に割り振れば良いので無視できる）
最低限必要な枚数がわかっていればそれ以上手札にあるかチェックすれば良い。

②a b cの数字の決定の仕方
手札が決まっているということは、a b c は（もし+が存在すれば）必ず存在するので、
a b cが手札のどの札かというのを適当に仮定してやると、数字が決まる。
この時別に同じ札を選んじゃったりしてても、①の方法でチェックして大丈夫なら、マッチしていることは明らかなので良い。

マッチしたパターンの加算

パターンはもちろん本当はもっと数が多いのを減らしているので、パターンマッチが成功した時はちゃんと計算して足さないといけない。

N=3 M=10
1 1 2 4 4

の時のパターンの数を数える。

まず、それぞれの数について
1→3C2
2→3C1
4→3C2
なので、3C2 * 3C1 * 3C2

あとは生成パターンにおける数がどのランクになるかの計算をする。
間隔が開いているのは2-4の間なので、この手札にあるランクをMの数字の列から取り出すのは

上の２つの枠が、矢印のどこに入るかを求めれば良い。
２つの枠は順番は変わってはいけないので、[矢印の数]C[上の枠の数]のようなことをすれば求まる
（ 今回は(7+1)C(2) ）
あとはそれぞれについて全部かけてやればよい。