SRM525 Div.1

結果

---(+0/-0) 0pts
1251->1191

次回はDiv.2。

300

外側から切っていくということは残せるのは長方形なので、
任意の部分長方形についてその内側をカウントすればいいのだが、

そこからそれを残すために移動する回数を求める方法を考えて迷走した。
任意の部分長方形について考えるのだから、普通に計算すればいいのだが、
なぜか特殊な場合があるのではないかと疑いすぎてしまった。
前2回コーナーケースに見事にハマっているので仕方ないのだが。

TLでは30^6って間にあうの？みたいな話もあるけど
部分長方形の総数は最大で31C2 * 31C2 ≒　2*10^5なので
2*10^5 * 30 * 30 = 1.8 * 10^8　ぐらいでまぁ間に合うだろうとか思っていた。

前処理をかけておけば領域内のコインの個数はO(1)で求められるみたい。

次回

またすぐDiv1に帰りたいと思います！

以下通したソースコード

class DropCoins {
     public:

     int getMinimum(vector <string> board, int K) {
         pair<int,int> lu, rd;
         int h = board.size();
         int w = board[0].size();
         int ret = 1<<29;

         for(int i=0;i<h;i++){
             for(int j=0;j<w;j++){
                 //左上の点(i,j)
                 for(int p=i;p<h;p++){
                     for(int q=j;q<w;q++){
                         //右下の点(p,q)
                         int count = 0;
                         for(int x=i;x<=p;x++){
                             for(int y=j;y<=q;y++){
                                 if(board[x][y] == 'o'){
                                     count++;
                                 }
                             }
                         }
                         if(count == K){
                             ret = min(ret, min(i,h-p-1)*2 + max(i,h-p-1) + min(j,w-q-1)*2 + max(j,w-q-1));
                         }
                     }
                 }
             }
         }
         if(ret == 1 << 29) ret = -1;
         return ret;         
     }