概要

選んだコンピュータのポート数を、そのまま木の各頂点の次数として実現できるかを判定する問題です。

結論として、答えが Yes になるのは次のどちらかの場合だけです。

• \(A_i = 0\) のコンピュータが \(1\) 台以上ある
• \(A_i = 1\) のコンピュータが \(2\) 台以上ある

考察

木における「次数」は、その頂点につながっている辺の本数です。
この問題では、選んだコンピュータ \(i\) の次数がちょうど \(A_i\) である必要があります。

1 台だけ選ぶ場合

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

したがって、そのコンピュータのポート数が \(0\) なら条件を満たせます。

つまり、どこかに \(A_i = 0\) があれば、答えは必ず Yes です。

2 台以上選ぶ場合

\(2\) 台以上のコンピュータを選ぶ場合、構築するネットワークは木です。

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

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

次数 \(1\) の頂点は「葉」と呼ばれます。

この問題では次数がそのまま \(A_i\) なので、選んだコンピュータの中に \(A_i = 1\) のものが少なくとも \(2\) 台必要です。

逆に、\(A_i = 1\) のコンピュータが \(2\) 台あれば、その \(2\) 台だけを選んでケーブルを \(1\) 本つなげばよいです。

このとき、両方のコンピュータの次数は \(1\) になり、木構造条件もポート使い切り条件も満たします。

例えば、

A = [3, 1, 5, 1]

なら、\(A_i = 1\) のコンピュータが \(2\) 台あるので、その \(2\) 台だけを選んで接続すれば Yes です。

一方、

A = [2, 3, 1]

では \(A_i = 0\) はなく、\(A_i = 1\) も \(1\) 台しかありません。
\(2\) 台以上の木には葉が少なくとも \(2\) 個必要なので、これは不可能です。

素朴な方法が不要な理由

全ての部分集合を試したり、次数列が木として実現可能かを判定したりする必要はありません。

なぜなら、条件を満たすためには次のどちらかが必要十分だからです。

• \(A_i = 0\) がある
• \(A_i = 1\) が少なくとも \(2\) 個ある

したがって、配列全体を一度見るだけで判定できます。

アルゴリズム

次のように判定します。

1. \(A_i = 0\) が見つかったら、即座に Yes
2. \(A_i = 1\) の個数を数える
3. \(A_i = 1\) が \(2\) 個以上になったら、即座に Yes
4. 最後まで見てもどちらも満たさなければ No

判定条件をまとめると、

0 が存在する または 1 が 2 個以上存在する

なら Yes、そうでなければ No です。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\) 追加メモリ

実装のポイント

入力サイズが最大 \(N = 10^6\) と大きいため、高速な入力を使っています。

この実装では sys.stdin.buffer.read() で入力全体を読み込み、数値を文字列として走査しています。

判定に必要なのは、各 \(A_i\) が \(0\) か \(1\) かだけです。
そのため、整数に変換せず、トークンが "0" または "1" かどうかだけを見ています。

if c == 48:  # '0'
    print("Yes")
if c == 49:  # '1'
    ones += 1

また、Yes が確定した時点で即座に終了することで、余計な処理を省いています。

ソースコード

import sys

def main():
    data = sys.stdin.buffer.read()
    n = len(data)
    i = 0

    while i < n and data[i] > 32:
        i += 1

    ones = 0

    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            break

        start = i
        while i < n and data[i] > 32:
            i += 1

        if i - start == 1:
            c = data[start]
            if c == 48:
                sys.stdout.write("Yes\n")
                return
            if c == 49:
                ones += 1
                if ones >= 2:
                    sys.stdout.write("Yes\n")
                    return

    sys.stdout.write("No\n")

if __name__ == "__main__":
    main()

---

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