SRM525 Div2Med DropCoins

問題概要
テーブルに有るコインを４方向にずらして枠外に振り落とせる。テーブル上に残るコインの数が、与えられた数Kに一致するための最小のテーブルの移動回数を求めよ。

解法
制約が小さく、テーブルが 30*30 なので単なる6重ループで求まるはずだが、二次元の累積和を取った4重ループでも解答可能。以下のコードは4重ループのコード。

またテーブルからコインを振り落とす際に盤面全体が移動していくので、四方向のうち反対の方向にずらそうとするときがあるので、それを注意して計算式を書く必要がある。解答では、押して引いた際に消費回数が小さい方向をみて、それを押し（引き）の分の２倍で求めている。

反省
600点問題だから少なくとも４重ループの二次元累積和の問題だろうと、勝手に身構えてオーダー計算見誤ってしまった。

#include <bits/stdc++.h>
using namespace std;

#define INF (1<<29)

class DropCoins {
public:
  
  int sum[52][52];
  int mat[52][52];
  
  int getMinimum(vector <string> board, int K) {
    
    int const H = board.size();
    int const W = board[0].size();

    memset(mat, 0, sizeof(mat));
    
    for(int i=1; i<=H; i++)
      for(int j=1; j<=W; j++)
        mat[i][j] = board[i-1][j-1] == 'o';
    
    memset(sum, 0, sizeof(sum));
    
    for(int i=1; i<=H; i++) {
      for(int j=1; j<=W; j++) {
        sum[i][j] = mat[i][j]
          + sum[i-1][j]
          + sum[i][j-1]
          - sum[i-1][j-1];
      }
    }
    
    int ans = INF;
    
    for(int i=0; i<H; i++)
      for(int j=0; j<W; j++)
        for(int k=i+1; k<=H; k++)
          for(int l=j+1; l<=W; l++)
            if(sum[k][l] - sum[k][j] - sum[i][l] + sum[i][j] == K) {
              int cand = min((W-l)*2+j, (W-l)+j*2) + min((H-k)*2+i, (H-k)+i*2);
              ans = min(ans, cand);
            }
    
    if(ans == INF) return -1;
    else return ans;
  }
};