C++で解くカードフリップゲーム：最小の「良い」数を求めるアルゴリズム

テーブルの上にN枚のカードが置かれており、各カードの両面には正の整数が印刷されています（表面と裏面で異なる数字の場合もあります）。まず任意の枚数のカードを裏返し、その後1枚のカードを選びます。選んだカードの裏面に書かれた数字Xが、どのカードの表面にも存在しないとき、その数字Xは「良い（good）」と呼ばれます。このとき、最も小さい「良い」数を求めるのがこの問題の目的です。良い数がひとつも存在しない場合は0を返します。ここで、fronts[i]とbacks[i]はそれぞれi番目のカードの表面と裏面の数字を表し、カードを裏返すと表面と裏面の数字が入れ替わります。

例えば、fronts = [1,2,4,4,7]、backs = [1,3,4,1,3]という入力の場合、出力は2になります。2枚目のカードを裏返すと、表面は[1,3,4,4,7]、裏面は[1,2,4,1,3]となります。この状態で2枚目のカードを選ぶと、その裏面には2が書かれており、2はどのカードの表面にも存在しないため、「良い」数であると言えます。

解法のアプローチ

この問題を解くためには、以下の手順に従います。

• 集合sを定義し、n := frontsのサイズ、ret := INT_MAX（無限大の扱い）と初期化する
• iを0からn-1まで繰り返す：fronts[i] == backs[i]の場合、fronts[i]を集合sに挿入する
• iを0からn-1まで繰り返す：fronts[i]がsに含まれない場合、ret := min(ret, fronts[i])とする
• iを0からn-1まで繰り返す：backs[i]がsに含まれない場合、ret := min(ret, backs[i])とする
• retがINT_MAXのままなら0を返し、それ以外はretを返す

このアプローチのポイントは、同じ数字が1枚のカードの表面と裏面の両方に現れている場合、その数字はどんなに裏返しても必ずどこかのカードの表面に現れてしまうため、決して「良い」数にならないという点です。そこで、まずそのような数字を集合sに集めて除外候補とし、残りのすべての数字（表面・裏面の両方）の中から最小値を求めます。計算量は時間・空間ともにO(n)で効率的です。

それでは、以下の実装例を見て理解を深めましょう。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int flipgame(vector<int>& fronts, vector<int>& backs) {
      set <int> s;
      int n = fronts.size();
      int ret = INT_MAX;
      for(int i = 0; i < n; i++){
         if(fronts[i] == backs[i])s.insert(fronts[i]);
      }
      for(int i = 0; i <n; i++ ){
         if(s.count(fronts[i]) == 0) ret = min(ret, fronts[i]);
      }
      for(int i = 0; i <n; i++ ){
         if(s.count(backs[i]) == 0) ret = min(ret, backs[i]);
      }
      return ret == INT_MAX? 0 : ret;
   }
};
main(){
   vector<int> v1 = {1,2,4,4,7};
   vector<int> v2 = {1,3,4,1,3};
   Solution ob;
   cout << (ob.flipgame(v1, v2));
}

入力

[1,2,4,4,7]
[1,3,4,1,3]

出力

2