概要

選んだコンピュータのポート数を「木の各頂点の次数」とみなせるかどうかを判定する問題です。
結論として、A_i=0 のコンピュータが1台でもあるか、または A_i=1 のコンピュータが2台以上あれば Yes、それ以外は No です。

考察

この問題は「ある部分集合を選んで、その次数列で木が作れるか？」と言い換えられます。

木に対して有名な性質として、頂点数を \(k\)、各頂点の次数を \(d_1,\dots,d_k\) とすると

\[ \sum_{j=1}^{k} d_j = 2(k-1) \]

が成り立ちます（辺数が \(k-1\) 本、次数和は辺数の2倍）。

---

まず、\(k=1\)（1台だけ選ぶ）場合を考えます。
このときケーブルは0本なので、使い切り条件を満たすにはその1台のポート数が0でなければなりません。
つまり A_i=0 が1つでもあれば即 Yes です。

---

次に \(k\ge2\) の場合。選んだ頂点は木の頂点なので、どの頂点も次数は少なくとも1です。
よって選ぶ頂点に A_i=0 は含められません。

ここで式を変形します。
\(w_i = A_i - 2\) とおくと、上の次数和条件は

\[ \sum (A_i - 2) = -2 \]

となります。
A_i の値ごとの \(w_i\) は：

• \(A_i=1 \Rightarrow w_i=-1\)
• \(A_i=2 \Rightarrow w_i=0\)
• \(A_i\ge3 \Rightarrow w_i\ge1\)

この和を \(-2\) にするには、負の値（\(-1\)）が少なくとも2つ必要です。
つまり A_i=1 が2個未満なら不可能。

逆に A_i=1 が2個以上あれば、その2台だけ選べば次数 \((1,1)\) の木（辺1本）が作れて条件を満たせます。
（A_i=2 を足しても和は変わらず、不要なら選ばなくてよい。）

したがって判定条件は非常に単純になります：

1. A_i=0 が1つでもある → Yes
2. そうでなく A_i=1 が2つ以上ある → Yes
3. それ以外 → No

---

素朴に「全部分集合」を試すと \(2^N\) 通りで、\(N\le10^6\) では不可能です。
上の次数和の性質を使うことで、配列を1回見るだけで判定できます。

アルゴリズム

1. cnt0（A_i=0 の個数）と cnt1（A_i=1 の個数）を数える。
2. cnt0 > 0 なら Yes を出力して終了。
3. そうでなければ、cnt1 >= 2 なら Yes、それ以外は No。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)（提示コードでは配列 A を保持しているため。カウントだけなら \(O(1)\) にもできる）

実装のポイント

• N が大きいので、ios::sync_with_stdio(false); cin.tie(nullptr); で高速入出力を使う。

• 実際の判定に必要なのは cnt0 と cnt1 だけなので、理論上は読みながら数えるだけで十分。

• A_i は最大 \(10^9\) だが、今回の条件判定では 0/1/それ以外 の区別だけでよい。

  ソースコード

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

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

    int N;
    cin >> N;
    vector<long long> A(N);
    long long cnt0 = 0, cnt1 = 0;
    bool has_ge2 = false;

    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        if (A[i] == 0) cnt0++;
        else if (A[i] == 1) cnt1++;
        else has_ge2 = true;
    }

    // k=1 case: choose one computer with A_i=0
    if (cnt0 > 0) {
        cout << "Yes\n";
        return 0;
    }

    // For k>=2 tree using all ports:
    // degree sequence must satisfy:
    // 1) all chosen degrees >=1 (already true since no zero in chosen set)
    // 2) sum(deg) = 2(k-1)  <=> sum(deg-2) = -2
    // Let w_i = A_i - 2.
    // Need non-empty subset (k>=2) with sum w_i = -2.
    // Here A_i>=1 for all i. Then:
    // A_i=1 => w_i=-1, A_i=2 => 0, A_i>=3 => >=1.
    // To make sum -2, we must include exactly two -1's and no positive net excess,
    // which is always possible iff there are at least two A_i=1 (choose those two,
    // optionally any number of A_i=2).
    if (cnt1 >= 2) cout << "Yes\n";
    else cout << "No\n";

    return 0;
}

---

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