概要

選んだコンピュータのポート数をすべて使い切って、選んだ頂点全体が木になるかを判定します。
結論として、\(A_i=0\) のコンピュータが存在する、または \(A_i=1\) のコンピュータが \(2\) 台以上存在すれば Yes です。

考察

まず、選ぶコンピュータの台数で場合分けします。

1 台だけ選ぶ場合

コンピュータを \(1\) 台だけ選ぶ場合、ケーブルは \(0\) 本です。

このときポートをすべて使い切る必要があるので、選んだコンピュータのポート数は \(0\) 個でなければなりません。

つまり、\(A_i=0\) のコンピュータが存在すれば、それを \(1\) 台だけ選ぶことで条件を満たせます。

2 台以上選ぶ場合

選んだコンピュータが \(k \geq 2\) 台のとき、ネットワークは木です。

木には重要な性質があります。

• 頂点数が \(2\) 以上の木には、次数が \(1\) の頂点、つまり葉が少なくとも \(2\) 個存在する

ここで、各コンピュータの次数は、使うケーブルの本数に等しいです。
また、ポートをすべて使い切る必要があるので、選んだコンピュータ \(i\) の次数はちょうど \(A_i\) になります。

したがって、\(k \geq 2\) 台を選んで木を作るなら、選んだ中に \(A_i=1\) のコンピュータが少なくとも \(2\) 台必要です。

逆に、\(A_i=1\) のコンピュータが \(2\) 台以上あれば、そのうち \(2\) 台だけを選び、1 本のケーブルで接続すればよいです。

このとき、

• 頂点数は \(2\)
• 辺数は \(1\)
• 両方の次数は \(1\)

なので、条件を満たす木になります。

素朴な方法が不要な理由

すべてのコンピュータの部分集合を試すと、最大で \(2^N\) 通りあり、\(N \leq 10^6\) では到底間に合いません。

しかし、上の考察により、必要なのは次の 2 つだけです。

• \(A_i=0\) が存在するか
• \(A_i=1\) が \(2\) 個以上存在するか

そのため、配列を一度見るだけで判定できます。

アルゴリズム

以下を順に行います。

1. has_zero を false にする
2. count_one を \(0\) にする
3. 各 \(A_i\) について
   • \(A_i=0\) なら has_zero = true
   • \(A_i=1\) なら count_one を \(1\) 増やす
4. 最後に、
   • has_zero が true
   • または count_one >= 2

のどちらかを満たせば Yes、そうでなければ No を出力する

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

\(N\) は最大で \(10^6\) なので、配列全体を保存する必要はありません。
入力を読みながら、\(0\) があるか、\(1\) が何個あるかだけを数えれば十分です。

また、\(A_i\) は最大で \(10^9\) なので、int でも扱えますが、コードでは安全に long long で読み込んでいます。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    bool has_zero = false;
    int count_one = 0;

    for (int i = 0; i < N; ++i) {
        long long A;
        cin >> A;
        if (A == 0) has_zero = true;
        if (A == 1) ++count_one;
    }

    cout << (has_zero || count_one >= 2 ? "Yes" : "No") << '\n';
    return 0;
}

---

この解説は gpt-5.5-xhigh によって生成されました。