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"; } } };