Codeforces #511 Div1 B. Little C Loves 3 II

しょうもないミスで落としてつらい。
http://codeforces.com/contest/1034/problem/B

問題

H*Wのグリッドがあったとする。
マンハッタン距離が３のマス同士をペアにすることができるとする。
ただし各マスは１つのマスとしかペアになれない。
最大で何個のペアを生成できるか。

解法

以下のように塗ることで、1*6、2*4、2*5、3*4の矩形を塗りつぶすことができる。

ABCABC

ACBD
BDAC

ADECD
BCABE

AEBA
BFCD
CDEF

以下H≦Wとする。

• H=1の場合、端から貪欲にペアを取れば解は自明。
• H=2の場合、2*4と2*5が作れることから、W=2,3,7のときは埋められないマスができて、それ以外はすべてペアを組める。
• H=3の場合、Wも奇数の場合は１マス残るが、それ以外はすべて埋めることができる。

ll H,W;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	if(H>W) swap(H,W);
	if(H==1) {
		ll ret=W/6*6;
		W%=6;
		if(W==4) ret+=2;
		if(W==5) ret+=4;
		cout<<ret<<endl;
	}
	else if(H==2) {
		if(W==2) {
			cout<<0<<endl;
		}
		else if(W==3 || W==7) {
			cout<<H*(W-1)<<endl;
		}
		else {
			cout<<H*W<<endl;
		}
	}
	else {
		cout<<H*W-(H*W%2)<<endl;
	}
	
}

まとめ

これ落としたのもったいないなぁ。