「問題 X の答えが Possible である」\(\Rightarrow\)「\(V\) の任意の部分集合 \(S\) に対して \(\left(\sum_{i\in S}D_i\right)-2e_G(S)\leq \sum_{i\notin S}\min(D_i,e_G(i,S))\) が成り立つ」の成立は明らかです．

よって予想Yが間違えるのは，「問題 X の答えが Impossible である」が，不等式条件は成立する，というときです． そこでまず，不等式条件の成立を確かめるアルゴリズムを考えます．

以降，\(e_G(i,S)\) を \(i \in S\) に対しても使用することにします（定義は同じです）．

\(f(S)=\left(\sum_{i\in S}D_i\right)-2e_G(S)- \sum_{i\notin S}\min(D_i,e_G(i,S))\) という量の最大値を取る \(S\) の中で極小なものを考えます． \(i \in S\) であって，\(D_i \leq e_G(i,S)\) を満たすものがある場合，\(S\) を \(S \setminus \{i\}\) に置き換えても \(f(S)\) が減少しないことから，\(S\) の極小性に矛盾します．

ここで，\(g(S) = \left(\sum_{i\in S}D_i\right)- \sum_{i \in V}\min(D_i,e_G(i,S))\) という量を考え，これの最大値を求めてみます． \(f(S)\) の最大値を取る \(S\) では \(i \in S\) に対して \(D_i > e_G(i,S)\) を仮定してよいことを示しましたが，同様にして，\(g(S)\) の最大値を取る \(S\) に対しても同じ条件を仮定できます． すると結局，\(f(S)\) の最大値と \(g(S)\) の最大値は等しくなります．

あとは \(g(S)\) の最大値が \(0\) かどうかを調べればよいですが，それは以下のように最大流の問題に帰着されます．

• 頂点 \(S,L_1,\ldots,L_N,R_1,\ldots,R_N,T\) からなるグラフを考え，以下のように辺を張る．
• \(S \to L_i\) に容量 \(D_i\) の辺
• \(R_i \to T\) に容量 \(D_i\) の辺
• \(G\) の各辺 \((u,v)\) に対して，\(L_u \to R_v\) および \(L_v \to R_u\) に容量 \(1\) の辺
• \(S\) から \(T\) への最大流の容量が \(\sum_i D_i\) であることと，\(g(S)\) の最大値が \(0\) であることは同値である．

最後の同値性は，このグラフの最小カットを考えることで示されます．

上述のグラフの最大流から，問題Xの半整数解を構築することが出来ます． 具体的には，\(L_u \to R_v\) に流量 \(1\) が流れている場合，元グラフの辺 \((u,v)\) の使用回数を \(+0.5\) すればよいです．

半整数解をできるだけ整数解に近づけましょう． 現在の使用回数が \(+0.5\) の辺だけを取り出してきたグラフを考えます． このグラフに偶数長の閉じたウォーク（頂点は重複してもよいが辺はすべて異なる）があった場合，辺の使用回数を \(0,1,0,1,\ldots\) と交互に設定することで，各頂点の次数を保ったまま整数解に近づけられます．

この操作を可能な限り行うと，残った辺たちは独立な奇数長のサイクルを構成します．

証明：次数 \(4\) 以上の頂点 \(v\) が存在すると仮定する．すべての頂点の次数は偶数なので，この頂点を含む連結成分のオイラーツアーを取ることができる．オイラーツアーを \(v\) で分離することで，\(2\) 個以上のウォークに分解できる．この中に偶数長のものは存在しない． しかし，奇数長のウォークを \(2\) つつなげれば，偶数長のウォークになるので，仮定に矛盾する．よって各頂点の次数は \(0\) または \(2\) であり，偶数長サイクルも存在しないことから，残った辺は頂点を共有しない奇数長サイクルを構成する．

次に，各奇数長半整数サイクルについて，その頂点間を結ぶサイクル以外の（つまり使用回数が \(0\) or \(1\) の）辺があった場合，それを使って解を組み替えることで，サイクル長を短くすることができます．

たとえば，半整数サイクルが \(a \to b \to c \to d \to e \to a\) で，使用回数 \(0\) の辺 \((a,c)\) が存在する場合，\((a,b),(b,c),(c,d),(d,e),(e,a),(a,c)\) の使用回数を \(1/2,1/2,0,1,0,1/2\) にすることで，サイクル長を \(3\) にできます．

また，ある二つの奇数長半整数サイクルについて，その間を結ぶ辺が存在する場合，それを使って解を組み替えて，\(2\) つの奇数長サイクルを消すことができます．

この操作を可能な限り行うと，各奇数長サイクルにはサイクル以外の辺が存在せず，また，サイクル間を結ぶ辺も存在しない状態になります．

今，奇数長サイクルが \(1\) つ以上残っているとします． ここで得た半整数解で使用回数が \(0\) の辺を \(G\) から削除します． すると，\(G\) は予想Yの不等式条件を満たすと同時に，問題Xの答えが Impossible となります．

この形のグラフ \(G\) を次数列 \(D_i\) から構成することを考えると，それは以下の手順で可能だと分かります．

• まず，いずれかの奇数長サイクルに含まれる頂点集合 \(C\) を選ぶ．\(C\) のサイズは \(6\) 以上の偶数である．
• \(C\) を奇数長サイクルに分解し，その辺の使用回数を \(1/2\) とする．また，サイクル以外の辺は \(C\) 内に張らない．
• \(C\) と \(V \setminus C\) の間，または \(V \setminus C\) 内部に使用回数 \(1\) の辺を張り，各頂点 \(i\) に接する辺の使用回数の合計を \(D_i\) にする．

ここで，\(C\) 内部の辺の張り方は判定に全く影響しません． そして，\(C\) の頂点数が \(8\) 以上だった場合，そのうち任意の \(6\) 頂点を \(C\) として取り直しても損しません． すると結局考えるべきは，次の手順だと分かります．

• サイズ \(6\) の頂点集合 \(C\) を取る．
• \(C\) 内に辺を張ってはいけないという条件で，\(C\) 内の頂点の次数を \(D_i-1\)，それ以外の頂点の次数を \(D_i\) にするグラフを構成する．

次に，候補となる \(C\) を絞ります． 実は，\(D_i\) の昇順に頂点を並べた際，\(C\) の候補としては隣接 \(6\) 頂点だけを考えれば十分です．

証明：頂点を \(D_i\) の昇順に並べ，この順に番号を付け直す．ある頂点集合 \(C\) を取ることで条件を満たすグラフ \(G\) が構成できるとする． \(x=\min(C),y=\max(C)\) として，\(y-x\) が最小の解を取る． \(C\) が隣接 \(6\) 頂点でないとすると，\(x<z<y\) かつ \(z\notin C\) である頂点 \(z\) が存在し，\(D_x < D_z < D_y\) が成り立つ．

\(z\) と結ばれている \(C\) 内の頂点数を \(t\) とする．\(t\leq1\) なら \(u=x\)，\(t\geq2\) なら \(u=y\) とし，\(C\) から \(u\) を除いて \(z\) を入れた集合を \(C'\) とする． \(z\) と結ばれている \(C\setminus\{u\}\) 内の頂点を \(a_1,\ldots,a_q\) とし，まず各辺 \((z,a_j)\) を消して \((u,a_j)\) を追加する．\(C\) 内には辺がないので，追加する辺はもともと存在しない．辺 \((u,z)\) が存在する場合，その辺は変更しない． この操作で \(z\) の次数は \(q\) 減り，\(u\) の次数は \(q\) 増える．目標はそれぞれ \(1\) 減らし，\(1\) 増やすことなので，\(W=V\setminus(C\cup\{z\})\) 内の頂点を使って次のように調整する．

• \(q=0\) の場合：このとき \(u=x\) であり，\(W\) 内の隣接頂点数は \(z\) の方が \(u\) より \(D_z-D_u+1\geq1\) 個多い．そこで \(z\) と結ばれ，\(u\) と結ばれていない頂点 \(b\in W\) を一つ選び，辺 \((z,b)\) を消して \((u,b)\) を追加する．
• \(q=1\) の場合：追加の調整は不要である．
• \(q\geq2\) の場合：このとき \(u=y\) であり，\(W\) 内の隣接頂点数は \(u\) の方が \(z\) より \(D_u-D_z+q-1\geq q-1\) 個多い．そこで \(u\) と結ばれ，\(z\) と結ばれていない頂点 \(b_1,\ldots,b_{q-1}\in W\) を選び，各辺 \((u,b_j)\) を消して \((z,b_j)\) を追加する．

いずれの場合も，自己ループや多重辺を作らずに，\(z\) の次数を \(1\) 減らし，\(u\) の次数を \(1\) 増やせる．ほかの頂点の次数は変わらず，\(C'\) 内には辺がないので，新しいグラフも条件を満たす． しかし \(\max(C')-\min(C')<y-x\) となり，最小性に矛盾する．

これで \(C\) の候補を \(O(N)\) 通りまで絞ることが出来ました． あとは各候補について実際にグラフが存在するかどうか判定すればよいです．

実はここで，予想Yを利用することが出来ます． \(C\) を一つ固定したときの問題は，それ自体が問題Xのインスタンスとして解釈できます． つまり：

• グラフ \(G\): 完全なグラフから \(C\) 内の辺を除いたもの
• 次数列 \(D'_i\): \(i \in C\) なら \(D'_i=D_i-1\)，それ以外は \(D'_i=D_i\)

というインスタンスです． そしてこの形のグラフでは予想Yが常に成立します．

これを使って各 \(C\) の候補について判定します．

\(C\) 外の頂点の次数を降順に並べた列を \(X\)，\(C\) 内の頂点の次数を降順に並べた列を \(Y\) とします．

まず，一つの \(X,Y\) が与えられたときの判定を考えます． 予想Yの不等式で試すべき \(S\) は，\(X,Y\) からそれぞれ prefix を取ってきた形です． ここで，\(L=|Y \cap S|\) を固定して，各 \(r=|X \cap S|\) に対し，不等号が持っている余裕 \(v_r\) を保持することにします．

この形にすると，\(X,Y\) に対する increment,decrement 操作が，\(v_r\) に対する区間加算で表現できるようになります． 具体的な式は解答例を参考にしてください．

そして，\(C\) の候補をずらす操作は，\(X,Y\) に対する increment,decrement 操作に対応します．\(C\) のサイズを \(U\) とする（\(U=6\) ですがわかりやすさのため変数を導入します）と，操作回数は，\(X\) の減算と \(Y\) の加算を合わせて \(O(UN)\) 回です．

\(L\) は \(0 \leq L \leq U\) の範囲をすべて試してやればよいです．

よって，すべての \(C\) 候補に対する判定を行うことができ，全体の時間計算量は \(O(U^2 N \log N)\) です．

解答例(C++)