Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2277-b628b360
この記事にトラックバックする(FC2ブログユーザー)

SRM552 DIV1 MEDIUM - FoxAndFlowerShopDivOne (この記事を編集する[管理者用])

Source

TopCoder SRM552 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

N*M (30*30以下) のグリッドが与えられる.
各マスは,空白か,PかLが書かれている.
2つの核軸に平行な長方形型の領域を選ぶ.この時,共通領域があってはいけない.
長方形に含まれているPの数とLの数の差はmaxDiff (900以下) 以下でなくてはいけない.
長方形に含まれているPの数とLの数の最大値を求める問題.
条件をみたすように長方形を選べないときはそれを指摘する.

解法

まず,重ならないように長方形を選ぶというのは,少なくてもx座標か,y座標が共通部分を持っていない.
つまり,2つの長方形を分断するように縦か横に線を引ける.
線の場所で全探索する.(横に線を引くとして,グリッドを回転して2回処理した)

まず,そのマスより左上の長方形領域に含まれるPの数,Lの数を前計算しておく.
すると,包除原理より,ある長方形領域に含まれるPの数,Lの数はO(1)で計算できる.

ある長方形領域を選ぶとき,Pの数 - Lの数が等しいなら,Pの数 + Lの数が大きいほうが良いから,Pの数 - Lの数をキーとして,Pの数 + Lの数の最大値をメモする.
長方形領域の最初の行と最後の行を固定した時でDPした後,最初からある行までの範囲でDPしたりした.

実装方法によるけど,だいたいO(30^4)~O(30^6)程度になる.(6乗は下手に書くとTLEかも)
以下のコードはO(30^5).

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define M 1000

int dp1[40][2000], dp2[40][2000];
int dp[40][40][2000];

class FoxAndFlowerShopDivOne {
public:
int theMaxFlowers(vector <string> mp, int maxDiff) {
  int i, j, k, loop;
  int x, y, x1, x2, y1, y2;
  int a, b;
  int res = -1;

  int cntP[40][40], cntL[40][40];

  rep(loop,2){
    x = mp.size();
    y = mp[0].size();

    rep(i,x+1) rep(j,y+1) cntP[i][j] = cntL[i][j] = 0;
    rep(i,x) rep(j,y){
      cntP[i+1][j+1] = cntP[i][j+1] + cntP[i+1][j] - cntP[i][j];
      cntL[i+1][j+1] = cntL[i][j+1] + cntL[i+1][j] - cntL[i][j];
      if(mp[i][j]=='P') cntP[i+1][j+1]++;
      if(mp[i][j]=='L') cntL[i+1][j+1]++;
    }

    rep(i,x+2) rep(j,2000) dp1[i][j] = dp2[i][j] = -1;
    rep(i,x) rep(j,x) rep(k,2000) dp[i][j][k] = -1;

    rep(x1,x) REP(x2,x1,x){
      rep(y1, y) REP(y2, y1, y){
        a = cntP[x2+1][y2+1] - cntP[x1][y2+1] - cntP[x2+1][y1] + cntP[x1][y1];
        b = cntL[x2+1][y2+1] - cntL[x1][y2+1] - cntL[x2+1][y1] + cntL[x1][y1];
        if(dp[x1][x2][M+a-b] < a+b) dp[x1][x2][M+a-b] = a+b;
      }
    }

    rep(i,x){
      if(i) rep(k,2000) dp1[i][k] = dp1[i-1][k];
      rep(j,i+1) rep(k,2000) if(dp1[i][k] < dp[j][i][k]) dp1[i][k] = dp[j][i][k];
    }

    for(i=x-1;i>=0;i--){
      if(i<x-1) rep(k,2000) dp2[i][k] = dp2[i+1][k];
      REP(j,i,x) rep(k,2000) if(dp2[i][k] < dp[i][j][k]) dp2[i][k] = dp[i][j][k];
    }

    REP(i,1,x){
      rep(k,2000) if(dp1[i-1][k] >= 0){
        a = 2*M - k - maxDiff;
        b = 2*M - k + maxDiff;
        if(a < 0) a = 0;
        if(b > 1999) b = 1999;
        REP(j,a,b+1) if(dp2[i][j] >= 0){
          if(res < dp1[i-1][k] + dp2[i][j]) res = dp1[i-1][k] + dp2[i][j];
        }
      }
    }

    {
      vector<string> hoge;
      string piyo;
      rep(i,x) piyo += ' ';
      rep(i,y) hoge.push_back(piyo);

      rep(i,x) rep(j,y) hoge[j][i] = mp[i][j];
      mp = hoge;
    }
  }

  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2277-b628b360
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。