SRM 265 DIV1 Hard PokerDeck - antaの競技プログラミング練習日記

問題

トランプのカード(ジョーカー無し)が"重複有り"で何枚か与えられる(decks)。
ここから5枚取った時に、ポーカーの役のそれぞれになる確率を求める。
確率が0より大きい役だけを、確率の低い順・同じなら辞書順順にvectorで返せ。
役は以下のものがある: {"ONE PAIR","TWO PAIR","THREE OF A KIND","FOUR OF A KIND","FIVE OF A KIND","FULL HOUSE","FLUSH","STRAIGHT","STRAIGHT FLUSH","ROYAL FLUSH","NOTHING"}
"STRAIGHT"では、"A,2,3,4,5"と"10,J,Q,K,A"は良くて、それ以外で巡回するものは認められない。"J,Q,K,A,2"や"Q,K,A,2,3"は駄目。
カードの重複が有りなので複数の役が重複することがある。その場合は"役の名前が辞書順で小さい方"になる。
ただし完全な包含関係にあるものは常により小さい方とする。
たとえば、"2S,2D,3S,3S,4S"は"ONE PAIR"とも"TWO PAIR"とも言えるが、("ONE PAIR" ⊃ "TWO PAIR")なので"TWO PAIR"になる。
たとえば、"2S 2S 2S 3S 3S"は"FULL HOUSE"や"FLUSH"になって、両者に包含関係は無いので、辞書順で("FLUSH" < "FULL HOUSE")なので"FLUSH"になる。

5 <= |decks| <= 800 (decksはvectorで与えられる)

解答

自分はコンビネーションと引き算でやった。
例えばあるフェイスを決めてその数を数え、(C(その数, 2) * C(n-その数, 3))で"ONE PAIR"の個数+αが出る。
重複を考えて最後に引く。ここが少し複雑。
フラッシュも考えないといけないのでさらに複雑になっている。

他に、C(52+5-1,5)(52枚からの重複有り組み合わせの数)が列挙可能なことを利用して「組み合わせの全てで役の判定をして、それにそれぞれのカードの数を掛ける」という解答もある。
こちらは役の重複は判定の部分ですればよいので明瞭でより良いと思う

(H(52,5) = C(56,5) = 3819816)や(C(52,5) = 2598960)が結構現実的な数であるというのは覚えておくべき

コード

自分の解答では、複雑でコピペの多く、悪いコードになっている

#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef long long ll; typedef vector<string> vs;
struct PokerDeck {
	vector <string> getRanking(vector <string> decks) {
		static ll C[888][888];
		mset(C, 0);
		rep(i, 888) {
			C[i][0] = C[i][i] = 1;
			reu(j, 1, i) {
				C[i][j] = C[i-1][j-1] + C[i-1][j];
			}
		}
		vector<pair<int,char> > d;
		each(i, decks) {
			stringstream ss(*i);
			char fc, s; int f;
			while(ss >> fc >> s) {
				if(s == '0') ss >> s, f = 10;
				else if(fc=='A') f = 1;
				else if(fc=='J') f = 11;
				else if(fc=='Q') f = 12;
				else if(fc=='K') f = 13;
				else f = fc-'0';
				d.pb(mp(f,s));
			}
		}
		enum {
			ONEPAIR,TWOPAIR,THREE,FOUR,FIVE,FULLHOUSE,FLUSH,STRAIGHT,STFLUSH,ROYAL,NOTHING,HANDS,FONEPAIR,FTWOPAIR,FTHREE,FFOUR,FFIVE,FFULLHOUSE,HANDS2
		};
		string names[] =
			{"ONE PAIR","TWO PAIR","THREE OF A KIND","FOUR OF A KIND","FIVE OF A KIND","FULL HOUSE","FLUSH","STRAIGHT","STRAIGHT FLUSH","ROYAL FLUSH","NOTHING"};
		ll hands[HANDS2] = {0};
		int n = d.size();
		char suits[4+1] = "CDHS";
		rep(s, 5) {
			int fcount = 0;
			if(s < 4) {
				rep(i, n) if(d[i].second == suits[s]) fcount ++;
				hands[FLUSH] += C[fcount][5];
			}
			rer(x, 1, 13) {
				int count = 0;
				rep(i, n) if(d[i].first == x && (s==4||d[i].second==suits[s])) count ++;
				if(s == 4) {
					hands[ONEPAIR] += C[count][2] * C[n-count][3];
					hands[THREE] += C[count][3] * C[n-count][2];
					hands[FOUR] += C[count][4] * C[n-count][1];
					hands[FIVE] += C[count][5];
				}else {
					hands[FONEPAIR] += C[count][2] * C[fcount-count][3];
					hands[FTHREE] += C[count][3] * C[fcount-count][2];
					hands[FFOUR] += C[count][4] * C[fcount-count][1];
					hands[FFIVE] += C[count][5];
				}
				rer(y, 1, 13) if(x != y) {
					int count2 = 0;
					rep(i, n) if(d[i].first == y && (s==4||d[i].second==suits[s])) count2 ++;
					if(s == 4) {
						if(x < y) hands[TWOPAIR] += C[count][2] * C[count2][2] * C[n-count-count2][1];
						hands[FULLHOUSE] += C[count][2] * C[count2][3];
					}else {
						if(x < y) hands[FTWOPAIR] += C[count][2] * C[count2][2] * C[fcount-count-count2][1];
						hands[FFULLHOUSE] += C[count][2] * C[count2][3];
					}
				}
			}
			rer(x, 1, 10) {
				ll t = 1;
				rep(j, 5) {
					int count = 0;
					rep(i, n) if(d[i].first == (x==10&&j==4 ? 1 : x+j) && (s == 4 || d[i].second == suits[s])) count ++;
					t *= count;
				}
				if(s == 4) hands[STRAIGHT] += t;
				else hands[STFLUSH] += t;
			}
			ll u = 1;
			rep(j, 5) {
				static const int royals[5] = {10,11,12,13,1};
				int count = 0;
				rep(i, n) if(d[i].first == royals[j] && d[i].second == suits[s]) count ++;
				u *= count;
			}
			hands[ROYAL] += u;
		}
		hands[ONEPAIR] -= hands[TWOPAIR];
		hands[ONEPAIR] -= hands[TWOPAIR];
		hands[ONEPAIR] -= hands[FULLHOUSE];
		hands[THREE] -= hands[FULLHOUSE];
		hands[STRAIGHT] -= hands[STFLUSH];
		hands[FLUSH] -= hands[STFLUSH];
		hands[FONEPAIR] -= hands[FTWOPAIR];
		hands[FONEPAIR] -= hands[FTWOPAIR];
		hands[FONEPAIR] -= hands[FFULLHOUSE];
		hands[FTHREE] -= hands[FFULLHOUSE];
		hands[ONEPAIR] -= hands[FONEPAIR];
		hands[TWOPAIR] -= hands[FTWOPAIR];
		hands[THREE] -= hands[FTHREE];
		hands[FULLHOUSE] -= hands[FFULLHOUSE];
		hands[FOUR] -= hands[FFOUR];
		hands[FLUSH] -= hands[FFIVE];
		hands[STFLUSH] -= hands[ROYAL];
		hands[NOTHING] = C[n][5];
		rep(i, HANDS) if(i != NOTHING) hands[NOTHING] -= hands[i];
		vector<pair<ll,string> > rr;
		rep(i, HANDS) if(hands[i] != 0) {
			rr.pb(mp(hands[i],names[i]));
		}
		sort(all(rr));
		vs r;
		each(i, rr) r.pb(i->second);
		return r;
	}
};

問題

解答

コメント

コード