Official
B - Full House 3 Editorial
by
B - Full House 3 Editorial
by
physics0523
解法1. 実際に \(5\) 枚選び出して試す
\(7\) 枚のカードから \(5\) 枚選び出して全探索します。
実装の方法はいくつかありますが、今回は bit 全探索 を利用します。
bit 全探索とは何かの説明は、以下のような解説記事に譲ります。
bit 全探索
bit全探索について簡単にまとめる
APG4b - AC - 3.05.ビット演算
\(7\) 枚のカードそれぞれについて「選ぶ」「選ばない」を指定し、以下の条件を判定します。
- カードがちょうど \(5\) 枚選ばれている。
- こちらは、 bit 全探索中に立っている bit の数を数えれば良いです。
- 選ばれたカードでフルハウスを作ることができる。
- こちらは、例えば選ばれたカード \(B_1,B_2,\dots,B_5\) をソートして以下のどちらかが成り立つか判定すれば良いです。
- \(B_1=B_2=B_3 \neq B_4=B_5\)
- \(B_1=B_2 \neq B_3=B_4=B_5\)
- こちらは、例えば選ばれたカード \(B_1,B_2,\dots,B_5\) をソートして以下のどちらかが成り立つか判定すれば良いです。
実装例 (C++):
#include<bits/stdc++.h>
using namespace std;
bool isFull(vector<int> &b){
sort(b.begin(),b.end());
if(b[0]==b[1] && b[1]==b[2] && b[2]!=b[3] && b[3]==b[4]){return true;}
if(b[0]==b[1] && b[1]!=b[2] && b[2]==b[3] && b[3]==b[4]){return true;}
return false;
}
int main(){
vector<int> a(7);
for(auto &nx : a){cin >> nx;}
for(int i=0;i<(1<<7);i++){
vector<int> b;
for(int j=0;j<7;j++){
if(i&(1<<j)){b.push_back(a[j]);}
}
if(b.size()==5){
sort(b.begin(),b.end());
if(isFull(b)){
cout << "Yes\n";
return 0;
}
}
}
cout << "No\n";
return 0;
}
解法2. フルハウスが作れる条件を精査する
まず、各カードが何枚あるかを調べます。このとき、フルハウスが作れる必要十分条件は次の通りです。
- 整数 \(x\) の書かれたカードが \(3\) 枚以上存在する
- さらに、 \(x \neq y\) であって整数 \(y\) の書かれたカードが \(2\) 枚以上存在する
これは、カードを登場頻度の多い方から順に並べ、
- 最も頻度の多いものが \(3\) 回以上登場するか
- 次に頻度の多いものが \(2\) 回以上登場するか
を判定すればよいです。
実装例 (C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int> bk(13,0);
for(int i=0;i<7;i++){
int x;
cin >> x;
bk[x-1]++;
}
sort(bk.rbegin(),bk.rend());
if(bk[0]>=3 && bk[1]>=2){cout << "Yes\n";}
else{cout << "No\n";}
return 0;
}
posted:
last update: