概要

\(N\) 台のコンピュータからいくつかを選び、すべてのポートを使い切る木構造のネットワークを構築できるかを判定する問題。ポート数 \(0\) のコンピュータが存在するか、ポート数 \(1\) のコンピュータが \(2\) 台以上存在するかで判定できる。

考察

木の性質を利用する

\(k\) 台のコンピュータで木を構成する場合、以下が成り立ちます： - 辺（ケーブル）の本数は \(k-1\) - 各頂点の次数（ポート使用数）の合計 = \(2(k-1)\)

つまり、選んだコンピュータのポート数を \(a_1, a_2, \ldots, a_k\) とすると、\(\sum a_i = 2(k-1)\) が必要です。

実現可能性の古典的結果

正の整数列 \(d_1, d_2, \ldots, d_k\) が \(\sum d_i = 2(k-1)\) を満たすなら、その次数列を持つ木が必ず存在します（Prüfer列の性質から導かれる古典的結果）。

場合分けによる網羅

\(k = 1\) の場合： \(A_i = 0\) のコンピュータを \(1\) 台選べばOK → \(cnt_0 \geq 1\)

\(k = 2\) の場合： \(a_1 + a_2 = 2\) かつ \(a_1, a_2 \geq 1\) なので、\(a_1 = a_2 = 1\) → \(cnt_1 \geq 2\)

\(k \geq 3\) の場合： ここが鍵です。選んだ値はすべて \(\geq 1\) で、合計が \(2(k-1)\) である必要があります。

• もし選んだ値がすべて \(\geq 2\) なら、合計 \(\geq 2k > 2(k-1)\)。不可能！
• もし選んだ値のうちちょうど \(1\) つが \(1\)、残りが \(\geq 2\) なら、合計 \(\geq 1 + 2(k-1) = 2k-1 > 2(k-1)\)。不可能！
• \(2\) つ以上が \(1\) なら可能性があるが、これは \(cnt_1 \geq 2\) を要求する（この場合、単に \(2\) 台の \(A_i = 1\) を選ぶ方が簡単）。

結論

答えが Yes となる必要十分条件は：

\[cnt_0 \geq 1 \quad \text{または} \quad cnt_1 \geq 2\]

アルゴリズム

1. 入力を読み込み、\(A_i = 0\) の個数 (\(cnt_0\)) と \(A_i = 1\) の個数 (\(cnt_1\)) を数える。
2. \(cnt_0 \geq 1\) または \(cnt_1 \geq 2\) なら Yes、そうでなければ No を出力。

具体例： - \(A = [0, 3, 2]\)：\(cnt_0 = 1 \geq 1\) → Yes（コンピュータ1を1台だけ選ぶ） - \(A = [1, 1, 5]\)：\(cnt_1 = 2 \geq 2\) → Yes（コンピュータ1と2を選び、1本のケーブルで接続） - \(A = [2, 3]\)：\(cnt_0 = 0, cnt_1 = 0\) → No

計算量

• 時間計算量: \(O(N)\)（配列を1回走査するだけ）
• 空間計算量: \(O(1)\)（カウンタのみ保持）

実装のポイント

• \(A_i\) の値が最大 \(10^9\) なので、入力は long long で受け取る。

• 条件判定は非常にシンプルで、カウントさえ正確に行えば良い。

• \(k \geq 3\) の場合を個別に探索する必要がないことが、この問題の本質的な気づきである。

  ソースコード

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    
    int cnt0 = 0, cnt1 = 0;
    for(int i = 0; i < N; i++){
        long long a;
        cin >> a;
        if(a == 0) cnt0++;
        if(a == 1) cnt1++;
    }
    
    if(cnt0 >= 1 || cnt1 >= 2){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    
    return 0;
}

---

この解説は claude4.6opus-thinking によって生成されました。