読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder, Single Round Match 668, Division 1, Leevl 1 : PaintTheRoom

問題概要

 $R \times C$ のグリッド状の盤面がある.この盤面上で,上下左右に隣接するセルにのみ移動することができる.任意のセルから始めて,任意のセルで終わる移動であって,全てのセルを丁度 $K$ 回ずつ通るものは存在するか?
 $R, C, K \leq 50$

解法

 まずは簡単な場合(かつ特殊な場合)として,$K = 1$ の場合を考えます.この場合は例えば,左上から始めて 1 行目を右端まで行って,一段下りて 2 段目を左端まで行く……というインベーダーっぽい動きをすることで全てのセルを丁度 $1$ 回ずつ通ることができます.
 $K \geq 2$ のときの基本戦略は,隣接する 2 セルをどちらも $K$ 回踏むまで往復して,次の 2 セルに進むというものになります.2 セルを $K$ 回往復するのを一塊と考えると,$R$ または $C$ が偶数のとき,偶数長の方に $2 \times 1$ の塊の $2$ の方を合わせれば先程の $K = 1$ の場合と同じ戦略で達成できます.
 残っているのは,$K \geq 2$ かつ $RC \bmod 2 = 1$ の場合ですが,この場合は目標を達成できません.左上を $( 0, 0 )$ として各セルに座標を割り当てて,各セル $( i, j )$ の $i + j$ の奇偶に着目します.盤面上の全ての移動は,偶数セルと奇数セルが交互に表れるので,どのように移動しても,途中に通った偶数セルの個数と奇数セルの個数の差は高々 $1$ になります.一方で,$RC$ が奇数のとき,盤面全体では奇数セルの方が 1 つ多く,全てのセルを $K$ 回ずつ通るような移動では,奇数セルの方が $K$ 回多く踏まれることになります.これは先程の条件に反するので,$RC \bmod 2 = 1$ のときは条件を満たす移動は存在しません.
 まとめると,$K \geq 2$ かつ $RC \bmod 2 = 1$ のときは達成不可能で,そうでないとき達成可能です.ちょっとした条件判定だけなので $O( 1 )$ で解くことができます.
 プログラミングの問題ではないですね.

コード

class PaintTheRoom
{
public:
	string canPaintEvenly( int R, int C, int K )
	{
		return 2 <= K && R * C % 2 ? "Cannot paint" : "Paint";
	}
};