ARC176 A - 01 Matrix Again
解法
どの列の総和も、どの行の総和も、$ Mにする必要がある。
ここで一つの事実を利用する:長さ$ Nの順列$ Pをとり、$ (1, P_1), (2, P_2), \ldots, (N, P_N)マスに$ 1を加えると、どの行の総和もどの列の総和も$ 1ずつ増える。
この順列として、具体的には、$ (k, k + 1, k + 2, \ldots, 1, 2, \ldots)を採用することにする。
すでに埋まっている$ M個のマスそれぞれに対して、ナナメ45°の同一直線上にあるマスも埋める。
これにより$ M本の直線ができれば、どの行もどの列も和は$ Mとなる。
この処理には$ O(NM)かかる。
マスの重複により直線の本数が足りない場合は、$ (1, k)のうちまだ使われていないものを選んで前述同様の処理を行う。
set等を使用することで、$ O(NM)で可能となる。
よって、この問題は$ O(NM)で解くことができた。