WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM668 Div1 Easy "PaintTheRoom"

解法

まず、K = 1ならば必ず"Paint"となる。

K >= 2であれば、R、C、どちらかが偶数であれば"Paint"となり、どちらも奇数であれば"Cannot paint"となる。
なぜどちらも奇数であれば"Cannot paint"であるかというと、まずR = C = 1であればSampleの通り自明である。
R >= 3 または C >= 3の場合について証明してみる。

教室のマス目が白黒で市松模様だったとする。白マスの数がW、黒マスの数がBとする。ちょうどK回ずつ塗らないといけないとなると、白マスの数をW * K回、黒マスの数をB * K回塗らないといけない。ここで、W != B かつ K >= 2なので、W * KとB * Kの差は2以上である。

移動方法が上下左右という事は、マス目は白→黒→白→黒→・・・と塗っていくことになり、塗ったマスで白マスの数と黒マスの数の差が2以上となることはありえない。

これより、R Cどちらも奇数の時、全てのマス目をK回塗る方法はないことになる。

ソースコード

class PaintTheRoom {
    public:
    string canPaintEvenly(int R, int C, int K) {
        bool isEven = (R * C) % 2 == 0;
        if (isEven || K == 1) {
            return "Paint";
        } else {
            return "Cannot paint";
        }
    }
};