概要

\(N\) 台のコンピュータからいくつかを選び、それらすべてを使い切って「木構造」のネットワークを構築できるかを判定する問題です。各コンピュータ \(i\) には \(A_i\) 個のポートがあり、選んだコンピュータはそのポートをすべて接続に使用する必要があります。

考察

この問題のポイントは、選ぶコンピュータの台数 \(k\) によって条件を整理することです。

1. 1台だけ選ぶ場合 (\(k=1\))

コンピュータを1台だけ選ぶ場合、ケーブルは0本です。 ポート使い切り条件を満たすためには、そのコンピュータのポート数 \(A_i\) が \(0\) である必要があります。 したがって、\(A_i = 0\) であるコンピュータが少なくとも1台存在すれば、Yes となります。

2. 2台以上選ぶ場合 (\(k \geq 2\))

\(k\) 台のコンピュータを選んで木構造を作る場合、以下の条件を満たす必要があります。

• 次数の総和: 木の性質より、ノードが \(k\) 個のとき辺の数は \(k-1\) 本です。各辺は2つのポートを消費するため、選んだコンピュータのポート数の総和は \(2(k-1)\) でなければなりません。
• 各ノードの次数: 木を構成するすべてのコンピュータは少なくとも1つの辺に接続されるため、選ぶコンピュータのポート数はすべて \(A_i \geq 1\) である必要があります。
• 葉の存在: 2台以上のノードからなる木には、必ず「葉」（次数が1のノード）が 2つ以上 存在します。

重要な気づき

「2台以上の木を構成できるか」を判定する際、実は 「ポート数が1のコンピュータが2台以上あるか」 だけを確認すれば十分です。

なぜなら、ポート数が1のコンピュータが2台あれば、それら2台を選ぶことで \(k=2\) の木（1本のケーブルで結ばれた構造）を確実に構築できるからです。このとき、ポート数の和は \(1 + 1 = 2\) であり、公式 \(2(k-1) = 2(2-1) = 2\) を満たします。

逆に、ポート数が1のコンピュータが0台または1台しかない場合、どのような \(k \geq 2\) 台の組み合わせを選んでも、木構造の「葉」が足りなくなる（あるいは次数の総和が \(2k-2\) を超えてしまう）ため、条件を満たすネットワークを構築することは不可能です。

アルゴリズム

1. 入力された \(A_1, A_2, \ldots, A_N\) を順番に確認します。
2. 以下のいずれかの条件を満たすか判定します。
   • \(A_i = 0\) となるコンピュータが1台以上存在する。
   • \(A_i = 1\) となるコンピュータが2台以上存在する。
3. 条件を満たせば Yes、そうでなければ No を出力します。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の要素を1回走査するだけで判定が可能なため、非常に高速です。
• 空間計算量: \(O(1)\)
  • 入力値をその場で処理すれば、追加の配列などは必要ありません（入力を保持する場合は \(O(N)\) となります）。

実装のポイント

• \(N\) が最大 \(10^6\) と大きいため、C++では std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); を用いて入出力を高速化しておくと安全です。

• \(A_i\) の値自体は \(10^9\) まで大きくなりますが、判定に必要なのは \(0\) か \(1\) か（あるいはそれ以外か）という情報だけなので、特別な型（long longなど）を意識せずに処理できます。

  ソースコード

#include <iostream>

/**
 * Problem: Network Construction
 * 
 * Logic:
 * 1. The problem asks if a subset of computers can be chosen to form a tree
 *    where each chosen computer $i$ uses exactly $A_i$ ports.
 * 2. If we choose a single computer ($k=1$), it must have $A_i = 0$ ports
 *    because a tree with 1 node has 0 edges.
 * 3. If we choose $k \ge 2$ computers, they must form a tree with $k-1$ edges.
 *    The sum of their degrees must be $2(k-1)$. Since it's a tree, every
 *    chosen computer must have at least one connection ($A_i \ge 1$).
 * 4. For a sequence $d_1, d_2, \dots, d_k$ to be the degree sequence of a simple tree,
 *    it must satisfy $d_i \ge 1$ and $\sum d_i = 2(k-1)$.
 * 5. The condition $\sum_{i \in S} A_i = 2|S| - 2$ with $A_i \ge 1$ implies that
 *    at least two of the chosen computers must have $A_i = 1$.
 *    Proof: Let $k = |S|$. $\sum (A_i - 1) = (2k-2) - k = k-2$.
 *    If we have $k_1$ computers with $A_i = 1$ (so $A_i - 1 = 0$), the remaining
 *    $k - k_1$ computers have $A_i - 1 \ge 1$. Thus, $\sum (A_i - 1) \ge k - k_1$.
 *    So $k - k_1 \le k - 2$, which means $k_1 \ge 2$.
 * 6. Therefore, a valid network can be built if and only if:
 *    - There exists at least one $A_i = 0$ (for the $k=1$ case).
 *    - There exist at least two computers with $A_i = 1$ (for the $k \ge 2$ case).
 *      If we have at least two $1$s, we can always form a tree with $k=2$ using them.
 */

int main() {
    // Optimize input and output performance
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N;
    if (!(std::cin >> N)) return 0;

    bool has_zero = false;
    int count_ones = 0;

    for (int i = 0; i < N; ++i) {
        int a;
        std::cin >> a;
        if (a == 0) {
            has_zero = true;
        } else if (a == 1) {
            count_ones++;
        }
    }

    // If there is any computer with 0 ports, we can pick just that one (k=1).
    // If there are at least two computers with 1 port, we can pick them (k=2).
    // Any larger tree (k > 2) also requires at least two computers with 1 port.
    if (has_zero || count_ones >= 2) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }

    return 0;
}

---

この解説は gemini-3-flash-thinking によって生成されました。