C - Row Column Sums ARC133
問題
H行W列のマス目について
各マスに0~K-1の整数を書き込もうとしている。
ここで以下の条件を満たす必要がある。
1<=i<=Hで、i行目のマスの整数の合計をKで割った余りはA[i]であり
1<=i<=Wで、i列目のマスの整数の合計をKで割った余りはB[i]である
条件を満たす様なマス目への書き込み方があるか判定し
あるなら、マス目の合計の最大値を求めよ
解答
まず、入力から全マスの合計をKで割った余りが分かる。
これはsum(A)%Kとsum(B)%Kであり、この二つが異なるなら答えは-1です。
次に各行について、あり得る合計の最大値を考える
任意のiについて、i行目のの合計は最大でも(K-1)*Wであるため
(K-1)*W以下でKで割った余りがA[i]に等しい整数があり得る最大値です。
各列についても同様にあり得る合計の最大値を求めます。
するとそれらの合計から
全ての行の合計としてあり得る最大値X
全ての列の合計としてあり得る最大値Y
が求まります
これらはつまるところ全てのマスの合計候補です
詳細は省きますが、X, Yが等しいなら実はXが答えになるような構築が出来ます。
よって今後はマス目の数を減らし、X, Yの値を同じにしていくことを考えます。
X, Yが等しくない場合、これらの差はKの倍数ですが
X>Yとして一般性を失わなず、そのうえで、D := X-Yとします
もし、Xの値をDだけ減らす事が出来れば答えはYです
この判定は、各行についての最大値を求める際に
合計をいくつまで減らせるかを求めておけば出来ます。
例えばK=5で、i行目の合計が最大で17であると求まった場合
その行は(17-A[i])/5*5までのKの倍数分なら減らせるといった具合です。
