SRM360 Div1 250

問題

数字の2次元配列が与えられる．その配列から各行と列がかぶらないように数字を選ぶ．そのとき，すべての組み合わせに対し，その選んだ数字の和がすべて等しいときCORRECT，違う場合INCORRECTを返す．

考え方

列iと列j，行kと行lを考える．(i,k)と(j,l)の数字を選んだ場合，残りは合計S'になるはず．(j,k)と(i,l)を選んでも残りの合計はS'になるはずなので，(i,k)+(j,l)と(j,k)+(i,l)が違う場合，合計が違ってしまうのでINCORRECT．
もし，すべての組み合わせに対して成り立つならば，(上の2つの場合を除いた残りの部分でも同様に成り立つので)，CORRECT．