SRM525 Div1 Easy - DropCoins
問題
タテhヨコwの長方形のいくつかのマスにコインが置いてある
「長方形全体を上下左右方向どれかに1マスぶん動かす」という操作ができ、その際に最初長方形があった領域からはみ出したマスに置いてあったコインは落下して消える
長方形に載ったコインの総数をk枚にするには最小で何回操作を行う必要があるか
(k枚にできない場合は-1を返す)
1 <= h,w <= 30
1 <= k <= 900
解法
操作を何度か行った結果できるのは元の長方形の上下左右を何行[列]か消してできる長方形
これを全通り試せばいい
各長方形に含まれるコインの数を数えるのは毎回やってるとO(h^3 w^3)になってキツイから二次元累積和を使う
今見てる長方形領域を切り出すために必要な操作回数の最小値は、仮にそれが上u行と下d行を削除した領域の場合、「上にu回ずらしてから下にu+d回ずらす」と「下にd回ずらしてから上にd+u回ずらす」のうち小さいほう(∴ min(u,d)*2+max(u,d))になる
列も同様に計算して足したもので答えを更新すればいい(もちろんコインの総数がkのときのみ)
class DropCoins { public: int getMinimum(vector<string> s, int k) { int h = s.size(), w = s[0].size(), a[33][33] = {}, res = inf; rep(i,h) rep(j,w) if (s[i][j]=='o') a[i+1][j+1]++; reps(i,1,h+1) reps(j,1,w+1) a[i][j] += a[i][j-1]; reps(i,1,h+1) reps(j,1,w+1) a[i][j] += a[i-1][j]; reps(i0,1,h+1) reps(j0,1,w+1) reps(i1,i0,h+1) reps(j1,j0,w+1) { int cnt = a[i1][j1] - a[i1][j0-1] - a[i0-1][j1] + a[i0-1][j0-1]; if (cnt!=k) continue; int mn = min(i0-1,h-i1) + min(j0-1,w-j1); int mx = max(i0-1,h-i1) + max(j0-1,w-j1); chmin(res, mn*2+mx); } return (res==inf ? -1 : res); } };