CODE FESTIVAL 2017 qualA B- fLIP

CODE FESTIVAL 2017 qualA B- fLIP

問題

提出AC

int main()
{
    cout << setprecision(10);
        
    int h , w , k;
    cin >> h >> w >> k;
    rep(i,h+1){//h行、w列
        rep(j,w+1){
            //まず、h行のうち一個も押さない（i = 0)
            int black = 0 ;
            black += (w-j) * i ;
            black += (h-i) * j ;
            if(black == k ){
                coY();
                return 0;
            }
        }
    }
    coN();
    
}

解法

問題文と違い、h行w列で考えてしまいましたが気にしないでください。

同じスイッチを二回押したら、結局押さない状態と同じになることに気が付く。

全部白の状態から考える

列に対しておいてあるスイッチを1つ押すと、その列がすべて黒になるので

黒いものはh個増えます。

この状態で、行に対してあるボタンを一つ（どの行のボタンでもよい）

押すと、1つが黒だったのが白に残りのw-1個は白から黒になります。

この時、増えた黒の数はw-2個であることが分かります。

実際に、h,wが3のとき

まず列に対して1つ押すと、3個黒ができる

次に行に対して1つ押すと、1個白が出来て、2個黒ができる

つまり黒は3個+(2-1)個 で4個になります

で、この問題の制約でh,wが小さいのでもう全部回しちゃえ。って考えます

行に対してボタンをi個、列に対してボタンをj個押したとき

行一つのボタンに対して増える黒の数は (w - j) * i

列1つのボタンに対して増える黒の数は ( h- i ) * j

です。 この式は、列に対するボタンをj個押すとき、行に対するボタン1つにつき黒くできるのは w - j 個という意味を

そして、行に対するボタンをi個押すとき、列に対するボタン1つにつき黒くできるのは

h - i 個ということを示しています。