AtCoder ARC #139 : C - One Three Nine

解けはしたけど手間取った…。
https://atcoder.jp/contests/arc139/tasks/arc139_c

問題

整数N,Mが与えられる。
以下を満たす点の集合の最大サイズを求めよ。

• 各点は格子点で、X座標は1以上N以下、Y座標は1以上M以下
• 各点iの座標を(X[i],Y[i])としたとき、X[i]+3*Y[i]の値は各点で異なっていなければならず、3*X[i]+Y[i]の値も各点で異なっていなければならない。

解法

X[i]+3*Y[i]や3*X[i]+Y[i]の取りえる値を考えると、取れる点はO(N+M)個程度であることが予想がつく。

試しに、(X座標+Y座標)が小さい順に貪欲に選ぶと、以下のようなパターンがでる。
対角線周辺に3*3の領域を取るようにしつつ、NとMに差がある場合、X座標またはY座標が最大の点を選んでいく。

ooo................
ooo................
ooooo..............
..ooo..............
..ooooo............
....ooo............
....ooooo..........
......ooooooooooooo

int N,M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	
	vector<pair<int,int>> V,W;
	
	for(i=0;i<=min(N,M);i+=2) {
		FOR(x,3) FOR(y,3) V.push_back({i+x,i+y});
	}
	FOR(i,100000) V.push_back({min(i,N-1),min(i,M-1)});
	
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	swap(V,W);
	FORR2(a,b,W) {
		if(a<N&&b<M) V.push_back({a,b});
	}
	
	
	cout<<V.size()<<endl;
	FORR2(y,x,V) cout<<y+1<<" "<<x+1<<endl;
	
}

まとめ

最初貪欲に選ぶ際、違う順で取ったら非最適解が出てしまい、WAを重ねる羽目に。