2011-11-30

SRM 525

16:54 |

cafelier さんとおなじ部屋。

o-- 114.8 Rank 562/794 1262->1259

300 DropCoins

16:54 |

部分矩形に含まれるoの数を矩形の大きそうな順に調べて最初に k 個だったのが答え...と当初思ったが違っていて時間がかかった。
左上原点から(x,y)までの矩形に入ってるoの個数の合計をv[y][x]に保存して４重ループにした（が他の人のを見てループ回数を数えて６重で問題ないことが判明..）
さらに、動かす最小の回数は四隅からの余白の合計 - 余白の最大値と当初思ったがこれも違っていて気づくまで時間がかかった
test case が通らないなと調べてるうちに、そもそも大きそうな順になってないじゃんと気付き、矩形の面積が大きいときの答えを優先するように変更
test case 4 だけ通らないなあと調べているうちに、面積と答えって関係ないじゃんと気づく
答えの最小値を調べればいいのだと気づく（そもそもそういう問題なのである）
わざわざ答えを全部覚えておいてソートして最初のやつを返すとかいってまわりくどい解答に。

とりあえず解くことはできたが時間がかかりすぎである。

思い込みで進めないでもっと考えるべきである。

class DropCoins {
	public:
	int getMinimum(vector <string> board, int K) {
		int W = board[0].size();
		int H = board.size();
		//cout<<W<<" "<<H<<endl;
		VVI v(H);
		REP(i, H) REP(j, W) v[i].push_back(0);
		REP(y, H) REP(x, W) {
			REP(yy, y+1) REP(xx, x+1) {
				v[y][x] += board[yy][xx]=='o' ? 1:0;
			}
		}
		VI ans;
		for(int sy=H;sy>0;sy--) {
			for(int sx=W;sx>0;sx--) {
				REP(by, H-sy+1) {
					REP(bx, W-sx+1) {
						int ax=bx-1;
						int ay=by-1;
						int ex=bx+sx-1;
						int ey=by+sy-1;
						int co=v[ey][ex];
						if(ay>=0) co-=v[ay][ex];
						if(ax>=0) co-=v[ey][ax];
						if(ax>=0 && ay>=0) co+=v[ay][ax];
						//cout<<" try "<<co<<" "<<bx<<" "<<by<<" "<<ex<<" "<<ey<<" area "<<sx<<" "<<sy<<endl;
						if(co==K) {
							int lans = 2*(bx+W-ex-1)-max(bx, W-ex-1) + 2*(by + H-ey-1) - max(by, H-ey-1);
							//cout<<"found "<<lans<<" "<<bx<<" "<<by<<" "<<ex<<" "<<ey<<" area "<<sx<<" "<<sy<<endl;
							ans.push_back(lans);
						}
					}
				}
			}
		}
		if(ans.size()==0) return -1;
		sort(ALL(ans));
		return ans[0];
	}

kojingharangの日記

2011-11-30

SRM 525

300 DropCoins