公式

B - Full House 3 解説 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\)

実装例 (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;
}

投稿日時:
最終更新: