ペペロを配ろう 2

小課題1 空きマス数を$K$とし、$2^K$通りを全探索して全生徒が両方の味を受け取るか確認する。時間計算量は$O(2^K NM)$である。

全体解法 各行と各列を頂点にし、空きマス$(i,j)$ごとに行$i$と列$j$を結ぶ辺を作る。横向きの箱は行頂点へ、縦向きの箱は列頂点へ辺を向けることに対応する。生徒がいる行・列の頂点を必須頂点と呼ぶ。条件はすべての必須頂点の入次数が正であることと同値である。

木の連結成分では辺数が頂点数より$1$少ない。全頂点が必須なら不可能である。必須でない頂点があれば、それを根として辺を子の方向に向ける。根以外の全頂点に入る辺ができる。

閉路を含む成分では全域木と木に含まれない辺$(r,c)$を選ぶ。$r$を根として木の辺を子方向に向け、選んだ追加辺を$r$に向ける。これですべての頂点に入る辺ができる。残りの辺の向きは任意でよい。孤立頂点も木の規則で扱える。

したがって、必須頂点だけからなる木成分がある場合に限り不可能である。DSUで全域森と追加辺を求め、根を選んで反復的に走査する。時間計算量は$O(NM\alpha(N+M))$、空間計算量は$O(NM+N+M)$である。

Solution written by GPT6.1