サーバルだよ！ AGC051C『Flipper』の解説をするよ！
コンテスト中の考察
なんだかライツアウトっぽいね。
ライツアウトと同じようなことをすれば解けそう。
ライツアウトをmod2での連立方程式だと思って解く方法と同じプログラムを書いて、6×6や7×7で実験をすると、ライツアウトの「解の存在条件」の式と同じようにして、今回の問題の操作での不変条件の式が出てくるんだけど、その式をぐ～～～っと睨むと、次の2つが不変量になってることがわかるよ。
・各列の黒マスの個数の偶奇
・各行の、「mod3で0の列と1の列にある黒マスの個数の合計の偶奇」「mod3で0の列と2の列にある黒マスの個数の合計の偶奇」
あとはこの不変量を崩さない条件も下で黒マスの個数を最小化すればいいね！
行の条件をもうちょっと丁寧に見ておこうかな。各行にあるmod3で0,1,2の列にある黒マスの個数を(x,y,z)で表すことにすると、「mod3で0の列と1の列の黒マスの個数の合計の偶奇」「mod3で0の列と2の列……」が、
・(偶,偶)なら(0,0,0),(1,1,1),……
・(奇,偶)なら(0,1,0),(1,0,1),……
・(偶,奇)なら(0,0,1),(1,1,0),……
・(奇,奇)なら(1,0,0),(0,1,1),……
になるよ。偶奇だけしか見てないから、例えば(偶,奇)なら(4,2,1)とかももちろん作れるね。
ということは、最初の盤面で上の4通りになってる行がそれぞれP,Q,R,S個、列について「黒マスの個数が奇数であるようなmod3で0,1,2の列の個数」をX,Y,Zとすると問題は次のように読み替えられるよ！
問題：
P,Q,R,S,X,Y,Zが与えられたとき、次の条件を満たすような(x,y,z)について、x+y+zの最小値を求めよ。
・(x,y,z)は、(0,0,0)か(1,1,1)をあわせてP個、(1,0,0)か(0,1,1)をあわせてQ個、(0,1,0)か(1,0,1)をあわせてR個、(0,0,1)か(1,1,0)をあわせてS個、(0,0,2),(2,0,0),(0,0,2)を好きな個数、合計したものである
・x≧X かつ y≧Y かつ z≧Z
・x≡X かつ y≡Y かつ z≡Z mod2
(Q,R,S)が考えられる最小なんだけど、x≧Xの条件とかを満たしてないときにどうするかを考えないといけなくて、(0,0,2)はタダで使えるけど+2だから、(1,0,0)を(0,1,1)に変える+1を優先するのが良くて、でも個数制限があって…………
というところで2時間悩んで本番中に結局解けなかったよ…………
コンテスト後の考察
まずQ=R=S=0のときはX+Y+Zが答えになることが少し考えるとわかるね。そうじゃないときを考えよう。
(Q,R,S)をベースに改善することを考えるんだけど、例えば(1,0,0)→(0,1,1)と(0,1,0)→(1,0,1)を両方やるのは(1,1,0)→(1,1,2)だから、(0,0,2)をタダでもらうのと同じになるね。
ということは結局、どの種類を何個変換するかを全探索すればOK！
Submission #19200670 - AtCoder Grand Contest 051 (Good Bye rng_58 Day 2)
うーん、数学でうまく最適解を求めるんじゃなくて、全探索すればよかったんだね……。前半パートがめちゃくちゃ数学だったから、すっかり数学頭になってたよ…………。
前半の考察の数学的な説明
あれ、今日は全部サーバルさんが解説すると思ってたんですが、数学パートは私がやるんですか？ いいですけど。
そういうわけで解説のスナネコです。
不変量を求めるときに登場した方程式が何をやっていたのかをちょっと説明します。
盤面をN×Nとして、各マスが白か黒かを0,1に対応させることで、盤面はのN^2次元ベクトルとみなすことが出来ます。
また、1回の操作も、操作によって変化するマスを1とするベクトルとみなすことで、盤面に対する操作は、ベクトルの足し算だと思うことが出来ます。
よって「操作に関する不変量を求めよ」という問題は、「(H-1)(W-2)種類の操作に対応するベクトルで張られる、の部分空間Vの元が満たすべき条件式を求めよ」になります。
(H-1)(W-2)個の操作が独立であることは少し考えるとわかります（ある元を、その元以外の線形結合で作ろうとしても、右下から貪欲に決めるしかなくうまくいかないことがわかります）。
なので、操作が張る部分空間の次元は(H-1)(W-2)であり、この部分空間の元が満たす条件式の個数はHW-(H-1)(W-2)=2H+W-2になります。
あとはサーバルさんがやったように実験をすると不変量っぽいものが見つかりますが、一応これが不変量であることを確認しておきましょう。
・列に関する条件の方は明らかですね。どの操作でも、各列のちょうど2マスが変化するので、黒マスの偶奇は変わりません。
・行に関する条件の方は、mod3で行を塗り分けるとわかります。どの操作でも、赤と青、赤と緑がちょうど2マス含まれるので、赤＋青、赤＋緑の部分にある黒マスの偶奇は変わりません。
列に関する条件式がW個、行に関する条件式が2H個で合わせて2H+W個あるように見えますが、列に関する条件のうち、右端2つの列の分は、他の条件から導くことができるので実質2H+W-2個です。
あとはこれらの条件が独立であることを確認すればよいですが、面倒なので省略します。
