AGC 016 C (+/- Rectangle) と Farkas' lemma
AGC 016 Cを考えていると気づいたことがあるので、紹介します。
まず、AGCの問題文 : C: +/- Rectangle - AtCoder Grand Contest 016 | AtCoder
この問題は要するに、局所的には負にしつつ、全体は正にする、というような気分のような問題です。
私も結局よくわからず、最後は答えを見てなるほど～～、と言っていました。
では次にFarkas' lemmaを見てみます。
Farkas' lemma - Wikipedia
これはリンクにある問題2つのうち、必ずどちらか一方のみに解がある、というなかなか面白い補題です。
この式の2番の方に着目してみましょう。として
で式を立てれば不等号の向きが入れ替わります。
さてこの式、AGCの方の問題とほぼ同じではないですか？
を要素がすべて1のベクトルすれば
は正にする制約だし、
側も、適切に設定すれば局所的に負にする制約にできます。
じゃぁこのとき、1式はどうなるのか。これは各小長方形1つに変数が1つ対応して、これがになります。
はマス1個に対応して、どの要素も1。
は小長方形の重み
をそれが含む各マスに足しこむ操作とみなせます。
ここまでわかれば、1式が解をもつかどうかはすぐにわかり、が
の倍数かつ
が
の倍数であることが必要十分になります。
すると、2式が解を持たないための条件はこの条件だとわかるのです。
ということで、解が存在する・しないの判定は、このようなアプローチで見つかることがわかりました。（やったね！）
AGCの問題を解こうと思うと、ここからさらに構成する必要があるのですが、
このアプローチだけだと少し厳しそうに見えます。
というのも、Farkas' lemmaのアプローチで解を構成しようと思うと、
分離超平面を構成する必要があります。
これを今回の大きさの行列に適用するのはしんどいので、特別な性質があればよいのですが、
ぱっとはわかりませんでした。
誰かわかる人がいれば教えてください。
