kmjp's blog

競技プログラミング参加記です

TopCoder SRM 668 Div1 Easy PaintTheRoom

今回は不参加。EasyもMediumも一発では通らなかったので、結果的には良かったのか。
http://community.topcoder.com/stat?c=problem_statement&pm=13846

問題

R*Cの2次元グリッドがある。
任意のマスで開始して隣接マスを順に辿り、各マスちょうどK回ずつ通ることはできるか。

解法

これとちょっと似てる。
yukicoder : No.85 TVザッピング(1) - kmjp's blog

回答から書くと、マスが偶数個またはK==1なら通ることができる。
マスが偶数個ある場合、2個の間をK往復したら次の2個に進む…と繰り返すと、Kが何であれK回ずつ通ることができる。
マスが奇数個の場合、その通り方はできないが、K==1なら全マスを順に辿るだけで済む。

ではマスが奇数個でKが2以上の時なぜ通れないかを考える。
上記TVザッピング同様、マス目を市松模様状に白黒2色で塗り分ける。
1回移動するたびに白黒交互に進むため、進む過程で白黒の通過マス数の差は1以下でなければならない。

ただし総マス数が奇数なら白と黒どちらかが1マス多く、それぞれをK回通るには白と黒どちらかをK回多く通ることになる。
これは上記ルールと矛盾する。
よって「マスが奇数個でKが2以上の時」は条件を満たす移動方法はない。

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

まとめ

なぜ一発ACできなかったのか。
TVはザッピングできても、床は塗れなかったようだ。
米国はCATV文化だしチャンネルは番号指定だから、全ボタンを1回ずつ押す、ということもないししょうがないよね。