TopCoder SRM 660 Div1 Easy Coversta

TCOに続き2連続やらかして大幅にレート減。
http://community.topcoder.com/stat?c=problem_statement&pm=13807

問題

N*Mの2次元グリッドがあり、各セルには0～9の数字が振られている。

ここでグリッド内のセル(sx,sy)を選んだとする。
パラメータとして、相対位置(x[i],y[i])の配列が与えられている。(要素数はK≦10)
(sx+x[i],sy+y[i])の数値の和が、選んだセル(sx,sy)のスコアだとする。

ここでセルを2つ選んだ時、スコアの総和の最大値を求めよ。
ただし、選んだ2つのセルに対する(sx+x[i],sy+y[i])が同一セルを2度指し示している場合、そこの数値は1回しかカウントされない。

解法

色々な解法がある。

まず、1個セルを選んだ時そのスコアがどうなるかを総当たりで調べよう。
またスコアの大きい順にソートしよう。
これはO(N*M*(K+logNM))である。

まず1個セルを総当たりで選ぶ。
もう1個のセルを選ぶ際、(sx+x[i],sy+y[i])が重複してしまうようなセルは高々K*(K-1)個である。

よって、もう1個のセルは最初に行ったセルのスコア順ソートのうち、上位(K*(K-1)+1)個まで探索すればセルが重複しないスコア最大ケースを必ず含む。
2つのセルを選んだ時のスコアの再計算にはO(K)かO(K*logK)程度かかるとすると、全体の計算量はO(N*M*K^3*logK)であり、Kが小さいので十分間に合う。

class Coversta {
	public:
	int H,W,N;
	int sum[101][101];
	vector <int> X,Y;
	vector <string> a;
	
	int dodo(int x1,int y1,int x2,int y2) {
		int i;
		int tot=0;
		vector<pair<int,int> > S;
		FOR(i,N) S.push_back(make_pair(y1+X[i],x1+Y[i]));
		FOR(i,N) S.push_back(make_pair(y2+X[i],x2+Y[i]));
		sort(S.begin(),S.end());
		S.erase(unique(S.begin(),S.end()),S.end());
		FORR(r,S) {
			if(r.first<0) continue;
			if(r.second<0) continue;
			if(r.first>=H) continue;
			if(r.second>=W) continue;
			tot += a[r.first][r.second]-'0';
		}
		return tot;
	}
	
	int place(vector <string> a, vector <int> X, vector <int> Y) {
		this->X=X;
		this->Y=Y;
		this->a=a;
		H=a.size(),W=a[0].size();
		N=X.size();
		vector<pair<int,pair<int,int> > > SS;
		
		int y,x,i,j;
		set<pair<int,int> > S;
		FOR(y,H) FOR(x,W) {
			sum[y][x]=0;
			FOR(i,N) {
				int cy=y+X[i],cx=x+Y[i];
				if(cy>=0 && cy<H && cx>=0 && cx<W) sum[y][x] += a[cy][cx]-'0';
			}
			SS.push_back(make_pair(-sum[y][x],make_pair(x,y)));
		}
		
		sort(SS.begin(),SS.end());
		if(SS.size()>105) SS.resize(105);
		int ma=0;
		FOR(y,SS.size()) FOR(x,y) ma=max(ma,dodo(SS[y].second.first,SS[y].second.second,SS[x].second.first,SS[x].second.second));
		return ma;
	}
}

まとめ

本番枝刈りの方法も危なくて時間ぎりぎりだったが、そもそも2か所も変数名ミスしてた時点で勝機はなかった。