行についてk
個のボタンを押す、列についてl
個のボタンを押すことを考えます。
行のボタンを押すと一行がすべて反転します。一行は列の数と同じだけのマスがありますので、反転するマスの数はM
個です。では、k
個の行ボタンを押した場合は、単純にk * M
個のマスが反転して、黒になります。
しかし、実際は列のボタンも押されています。先ほどのk * M
個のマスのうち、列ボタンも押されているマスがいくつあるのかを考える必要があります。なぜなら、これらのマスは行と列の両ボタンが押されているため、二回反転して白になっているからです。つまり、列ボタンも押されているマスの分だけ、減らさなくてはなりません。
その数の考え方は一緒です。一行に列ボタンも押されているマスの数は、そのまま列ボタンを押した数のl
個です。よって、これもk
個の行ボタンがおされれば、k * l
となります。あとはこれを引くだけです。ということで、行ボタンが押されたことによって生じる黒マスの数はk * M - k * l
つまりk * (M - l)
となりました。
次に列についてですが、全く同じ考え方ができます。行ボタンを考慮しない場合の黒マスはl * N
個、行ボタンも押されているマスはl * k
となり、あとは引き算をするだけ、l * N - l * k
つまり(N - k) * l
です。
最後に行と列それぞれで求めた黒マスの足し合わせます。
k * (M - l) + (N - k) * l
これがk
個の行ボタンとl
個の列ボタンを押したときの黒マスの数になります。あとは、求めているK
(入力で与えられる方です)個になるようなk
とl
の組合せがあるかを探すだけになります。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2017/09/24 07:36
2017/09/24 09:07
2017/09/24 09:45
2017/09/24 10:04