ペペロを配ろう

小課題1 空きマス数を$K$とする。$2^K$通りの向きを全探索し、横向きの箱がある行と縦向きの箱がある列を記録して全生徒を確認する。計算量は$O(2^K NM)$である。

全体解法 すべての行に空きマスがあれば、箱をすべて横向きにする。各生徒は自分の行の箱から受け取れる。同様に、すべての列に空きマスがあれば、箱をすべて縦向きにすればよい。

どちらの条件も満たさないなら、空きマスのない行と空きマスのない列が存在する。その交点の生徒はどちらの方向からも受け取れないので不可能である。よって判定も構成も正しい。

入出力を含む時間計算量は$O(NM)$、マス目を保存する空間計算量は$O(NM)$である。

Solution written by GPT6.1