SRM636に参加。
Easy早解き逃げ切りでレート上昇という、久々に自分らしいスタイルだった。
Mediumはsubmitにすら至らなかったのが残念。
http://community.topcoder.com/stat?c=problem_statement&pm=13497
問題
N*Mのグリッド状のチョコレートがあり、それぞれのセルは0-9のおいしさである。
このチョコレートに対し、縦に2本、横に2本切込みを入れて9個に分割したとき、分割した各領域のおいしさの和のうち、最小のものが自分のものになる。
最適な切込みを入れることで、自分が得られる領域のおいしさの総和の最大値を求めよ。
解法
事前にO(HW)かけて2次元の累積和を取っておけば、各領域のおいしさの総和をO(1)でとれるようになる。
後は分割位置を総当たりするだけ。
よってO(H^2*W*2)で回答可能。
int S[60][60]; class ChocolateDividingEasy { public: int sum(int x1,int y1,int x2,int y2) { return S[y2][x2]-S[y1][x2]-S[y2][x1]+S[y1][x1]; } int findBest(vector <string> C) { int H=C.size(), W=C[0].size(); int x,y,mi=0; ZERO(S); FOR(y,H) { FOR(x,W) S[y+1][x+1]=S[y+1][x]+C[y][x]-'0'; FOR(x,W) S[y+1][x+1]+=S[y][x+1]; } int x1,x2,y1,y2; for(y1=1;y1<=H;y1++) for(y2=y1+1;y2<=H;y2++) { for(x1=1;x1<W;x1++) for(x2=x1+1;x2<=W;x2++) { int v=99999999; v=min(v,sum(0,0,x1,y1)); v=min(v,sum(x1,0,x2,y1)); v=min(v,sum(x2,0,W,y1)); v=min(v,sum(0,y1,x1,y2)); v=min(v,sum(x1,y1,x2,y2)); v=min(v,sum(x2,y1,W,y2)); v=min(v,sum(0,y2,x1,H)); v=min(v,sum(x1,y2,x2,H)); v=min(v,sum(x2,y2,W,H)); mi=max(mi,v); } } return mi; } }
まとめ
久々にえらい安直なEasyが出たな。