猫の発言と帽子の色の整合性を判定するC++プログラム

問題の概要

N個の要素を持つ配列Aがあるとします。ここにN匹の猫がいて、1からNまでの番号が付けられています。すべての猫は帽子を被っており、i番目の猫は「自分以外のN−1匹の猫が被っている帽子の中には、ちょうどA[i]種類の異なる色が存在する」と発言します。このとき、すべての猫の発言と矛盾しない帽子の色の割り当てが存在するかどうかを判定するのがこの問題です。

たとえば、入力が A = [1, 2, 2] の場合、答えは True（真）になります。猫1・猫2・猫3がそれぞれ「赤・青・青」の帽子を被ることで、全員の発言と整合するためです。

解法のアプローチ

この問題は、配列内の最小値・最大値とその出現回数に着目することで効率的に判定できます。手順は以下のとおりです。

1. 配列Aの最小値 mn、最大値 mx、そして最小値と等しい要素の個数 cnt を求めます。
2. mx == mn の場合（すべての値が同一）：mn == n − 1 または 2 × mn ≤ n が成り立てば true、そうでなければ false を返します。
3. mx == mn + 1 の場合：mn ≥ cnt かつ n − cnt ≥ 2 × (mx − cnt) が成り立てば true、そうでなければ false を返します。
4. それ以外の場合：false を返します。

擬似コード

mn := 無限大, mx := 0, cnt := 0
n := 配列Aのサイズ
サイズ(n + 1)の配列aを定義
i := 1 から n まで繰り返す:
    a[i] := A[i - 1]
    mn := mn と a[i] の最小値
    mx := mx と a[i] の最大値
i := 1 から n まで繰り返す:
    もし a[i] が mn と等しいなら:
        cnt を 1 増やす
もし mx が mn と等しいなら:
    もし mn が n - 1 と等しい、または 2 * mn <= n なら:
        true を返す
    そうでなければ
        false を返す
そうでなく mx が mn + 1 と等しいなら:
    もし mn >= cnt かつ n - cnt >= 2 * (mx - cnt) なら:
        true を返す
    そうでなければ
        false を返す
それ以外なら
    false を返す

判定条件のポイント

• すべての猫が同じ値を報告している場合（mx == mn）は、「全帽子が同色」（その場合、各猫からは n − 1 色に見える）か、複数の色が適切な比率で混在する状態（2 × mn ≤ n）が考えられます。
• 報告値が2種類に分かれる場合（mx == mn + 1）は、最小値を報告する猫cnt匹と残りの猫の数の兼ね合いから、mn ≥ cnt かつ n − cnt ≥ 2 × (mx − cnt) という条件が導かれます。
• 報告値が3種類以上に分かれることは論理的にあり得ないため、その時点で false となります。

C++による実装例

理解を深めるために、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> A) {
    int mn = 99999, mx = 0, cnt = 0;
    int n = A.size();
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        a[i] = A[i - 1];
        mn = min(mn, a[i]), mx = max(mx, a[i]);
    }
    for (int i = 1; i <= n; ++i)
        if (a[i] == mn)
            ++cnt;
    if (mx == mn) {
        if (mn == n - 1 || 2 * mn <= n)
            return true;
        else
            return false;
    }
    else if (mx == mn + 1) {
        if (mn >= cnt && n - cnt >= 2 * (mx - cnt))
            return true;
        else
            return false;
    }
    else
        return false;
}
int main() {
   vector<int> A = { 1, 2, 2 };
   cout << solve(A) << endl;
}

入力

{ 1, 2, 2 }

出力

1

出力は 1（true）となり、入力 A = [1, 2, 2] に対して条件を満たす帽子の色の割り当てが存在することが確認できます。