No.3220 Forest Creation

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 37
作問者 :

Nauclhlt🪷 / テスター : 👑

p-adic

ProblemId : 12385 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2025-08-02 00:03:27

土着神であるケロちゃんは森を創造することができます。

ケロちゃんは以下の条件を満たす森をつくろうとしています。

そのようなことが可能かどうか判定してください。ただし、ケロちゃんは任意の森をつくることができるとします。

より形式的な問題文

無向グラフ $G$ であって次の条件をすべて満たすようなものは存在するか判定してください。

$G$ は閉路を含まない
$G$ に含まれる頂点であって、次数が $i$ であるものの個数を $D_i$ としたとき、任意の $i(0\leq i\leq N)$ に対して $A_i=D_i$ かつ $N<i$ に対して $D_i=0$

コンテスト本番時点では「$N<i$ に対して、次数 $i$ の頂点の個数に関する制約はありません。」の一文が代わりに入っていましたが、赤字部分の内容に修正しました。
場合によっては問題の内容自体が異なっているとも解釈できるため、これが原因で不正解になってしまった方、本当にすみませんでした……。

次数 $N$ 超過の頂点がいくらあっても良いと解釈すると、$N=1, A=(0, 9)$ なども Yes となってしまいますが、作問時点の問題の意図としては No でした
$N<i$ の言及なしでは少し曖昧ということになり一文追加しましたが、その際に表現を誤ってしまいこのような状態になっていました

$N$
$A_0\ A_1\ A_2\ \cdots\ A_N$

条件を満たす森をつくれるならYes、そうでないならNoを $1$ 行に出力してください。

最後に改行してください。

3
0 5 1 1

Yes

例えば、次のようなグラフを作ればよいです。

   o        o
  /         |
 o - o  o - o - o

2
0 0 3

No

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。