SRM489 Div2 500

問題

バラとユリをグリッドの花壇に植えるために花屋さんで箱買いする．i番目の箱にはバラがroses[i]本とユリがlilies[i]本入ってる．いくつかの箱を買って長方形の花壇に植えるが，制約として隣り合う花は違う種類にしなければならない．このとき作ることができる花壇の縦と横の差が小さくなるようにしたい．可能な縦と横の差の最小値を返す．作ることができない場合は-1を返す．

考え方

いくつかの箱を買った時のバラの本数とユリの本数を考える．これはdfsで買った場合と買わなかった場合として生成できる．
隣同士が違うように長方形を作るためにはバラとユリの本数の差が1以下でなければならない．
もし，バラとユリの本数の差が1以下の場合，作ることのできる長方形は，バラとユリの本数の和をsumとすると，sum=W*Hと分解できる．分解するには約数をWとしてH=sum/Wで出せる．あとはabs(W-H)が最小となるものを探す．見つからなければ-1．