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か所も変数名ミスしてた時点で勝機はなかった。