はじめに
これすっげぇおもしろい．
純粋に構築で面白いと思ったの本当に始めてクラス．（いつも構築は解けないので）
問題概要
n
{d1, d2, ... , dn}
が与えられます．
dn + 1 頂点のグラフを構築してください．多重辺，自己ループは認めません．
最後に，グラフの次数を全てsetに突っ込みます．その時，setの内容が与えられた，{d1, ... , dn}と同じになるようにしてください．
この時，必ず条件を満たすようなグラフが構築可能です
↑これ，めちゃめちゃ大事です．（問題でこの文言が与えられています）
考察
とりあえず例を考えます．
d ={2, 4, 5}のような場合を考えます．最初にdn+1頂点を用意しましょう．最初はすべて次数0です．
次数 = [0, 0, 0, 0, 0, 0]
この時，次数5の頂点を作るには1頂点選んで，他の頂点に全て辺を張るしかありません．
ですので，そのように辺を張り，例えば，
次数 = [1, 1, 1, 1, 1, 5]
のような状態になります．
この時，重要な考察なのですが，もう一番右の頂点には辺を張ることができません．多重辺，自己ループは許されないため．
そして，この後，辺を張ることを考えるのですが，頂点6にはもう辺を張れないので，これを以降無視していいです．
そして，それ以外の頂点にはもう次数が1増えているので，以下のような問題を次に解けばよいです．
d={1, 3, 4}
次数 = [0, 0, 0, 0, 0]
これは，dの要素を全て1引いて，頂点6を除外した姿です．
ではまた，解いていきましょう．同じように，dの最も大きい要素が，頂点数-1に等しいので，同じような操作を行います．
次数 = [1, 1, 1, 1, 4]
になります．
グラフ全体としては以下のようになります
同じように頂点を除外します
次に解くのは以下のような問題です．
d = {0, 2, 3}
次数 = [0, 0, 0, 0]
この時なのですが，dの内容物に0が含まれています．
ですので，頂点を1個，これ以降その頂点に辺を張らずに，そのまま残しておきたいです．よって一番左の頂点を残すこととします．
よって上の画像の頂点1をこれ以降触れません．除外します．
次に解くのは
d = {2, 3}
次数 = [0, 0, 0]
となりました．
で，もうこの状況で次数3の頂点は作れません．dからpopします．
d = {2}
次数 = [0, 0, 0]
を解いていけばいいです．
同じように，解いていけば，最終的に以下のようなグラフが出来上がって終わりです．
次数は最終的に，
次数 = [2, 4, 4, 4, 5, 5] となります．
Submission #98207940 - Codeforces
まとめ
問題で，与えられる入力に対しては必ず答えがあると証明できるといわれているのでガンガン1つの頂点の次数を決めて，再起的に小さい問題を構築することができれば，解ける，というのがこの問題のおもしろポイントだと感じています．
不可能なら不可能と示せ，と言われると，一段と難しくなるような気もします．わかりません．
とりあえず面白かったです．
