SRM 668 div1 easy:PaintTheRoom

SRM 668 に参加しました。結果は easy 正解 + challenge 3 回成功で 38 位という良い順位を取れました。
嬉しいんですが, med はほぼ正解にたどり着いていたので med を落としたのが残念です。今度は med も正解したい…

問題

R*C のグリッドを考える。

スタートする場所はどこでも良いので, R*C のセル全てにちょうど K 回ずつたどり着きたい。このようなことは可能か。

解法

結論を言うと, K==1 の時は OK, K > 1 のときは R*C が奇数の時は NG, 偶数の時は OK, です。

証明をしてみます。

K==1 の時は OK なことは明らかでしょう。

R*C が奇数の時, グリッドを市松模様にすると, 白色のセルが黒色のセルより 1 つ多くなります。よって, 条件を満たすためには, 白色のセルを黒色のセルより K 回多く踏まなければならないわけです。ですが, 白色と黒色のセルは交互に踏まれるので, K > 1 のときはこのようなことはありえません。よって, R*C が奇数の時は NG です。

また, R*C が偶数の時は, 例えば C が偶数の時は
(0, 0), (0, 1), (0, 0), (0, 1), (0, 2), (0, 3), (0, 2), (0, 3), ..., (0, C-1), (0, C), (0, C-1), (0, C),
(1, C), (1, C-1), ...

というような感じで踏んでいけば OK であることがわかります。

得た知見

• グリッドでは市松模様考えるのは典型だった。

本番書いたコード↓証明してないので不安になっていろいろ書いてます。

const string P = "Paint", N = "Cannot paint";

class PaintTheRoom {
public:
    string canPaintEvenly(int R, int C, int K) {
        if (R == 1 && C == 1) {
            if (K == 1) return P;
            else return N;
        }
        if (R > C) swap(R, C);
        if (R%2 == 0 || C%2 == 0) return P;
        if (K == 1) return P;
        return N;
    }
};