B - ネットワーク構築 / Network Construction Editorial
by 
MMNMM
\(3\) 台以上を選んで条件を満たすネットワークを構成できるなら、そのうち \(2\) 台を選んで条件を満たすネットワークを構成できることを示します。
証明
\(k\) 台 \((3\le k)\) 選んで条件を満たすネットワークを構成できたとします。
\(2\) 台を選んで条件を満たすネットワークを構成できることは、ポート数がちょうど \(1\) であるコンピュータが \(2\) つ存在するということです。
\(k\) 頂点の木の辺の本数は \(k-1\) 本なので、選んだコンピュータにおけるポート数の合計は \(2\times(k-1)=2k-2\) です。 木は連結なので、選んだコンピュータのポート数はどれも \(1\) 以上です。
ポート数がどれも \(1\) 以上である \(k\) 個のコンピュータについて、ポート数の合計がちょうど \(2k-2\) となるためには、ポート数がちょうど \(1\) であるコンピュータが \(2\) つ以上存在しなければなりません（そうでなければ、少なくともポート数は \(2k-1\) 以上となってしまいます）。
よって、\(2\) 台を選んで条件を満たすネットワークを構成できることが示されました。
よって、\(1\) 台以上を選んで条件を満たすネットワークを構成できることは、\(1\) 台もしくは \(2\) 台を選んで条件を満たすネットワークを構成できるということです。 さらに言い換えると、これは次のどちらかを満たすことと同値であることがわかります。
- \(A _ i=0\) であるコンピュータが存在する。
- \(A _ i=1\) であるコンピュータが \(2\) つ以上存在する。
あとは、この条件を満たすか for 文などで判定を行うことでこの問題を解くことができます。
実装例は以下のようになります。
#include <iostream>
using namespace std;
int main() {
int N;
cin >> N;
// ポート数が 0 のコンピュータの個数とポート数が 1 のコンピュータの個数をそれぞれ数える
int zero = 0, one = 0;
for (int i = 0; i < N; ++i) {
int a;
cin >> a;
if (a == 0) {
++zero;
}
if (a == 1) {
++one;
}
}
// 条件を判定して出力
if (zero < 1 && one < 2) {
cout << "No" << endl;
} else {
cout << "Yes" << endl;
}
return 0;
}
N = int(input())
# ポート数が 0 のコンピュータの個数とポート数が 1 のコンピュータの個数をそれぞれ数える
zero = 0
one = 0
for a in map(int, input().split()):
if a == 0:
zero += 1
if a == 1:
one += 1
# 条件を判定して出力
if zero < 1 and one < 2:
print('No')
else:
print('Yes')
posted:
last update: