Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Open 2011 Algorithm Qual. 3 HARD - ComplementMachine2D (この記事を編集する[管理者用])

Source

TopCoder Open 2011 Algorithm Qualification Round 3 HARD (1000pt)
Problem Statement
TopCoderニコ生オープン TCO11 Qual. 3 自分の参加記録

問題概要

01のみからなる行列で,以下の操作を考える.
 ある行より上の行に含まれる全ての要素の01を反転させる
 ある行より下の行に含まれる全ての要素の01を反転させる
 ある列より右の列に含まれる全ての要素の01を反転させる
 ある列より左の列に含まれる全ての要素の01を反転させる
この操作を繰り返して,全ての要素が0にできる行列をerasableと呼ぶ.
40*40以下の行列が与えられるので,そのerasableな部分行列の中で要素数の最大値を求める問題.
部分行列とは,行列から,最初の数行,最初の数列,最後の数行,最後の数列を取り去った行列.

解法

いくつかの行,列をブロックとみなして,市松模様っぽくなっていれば可能.
それを愚直に,全ての部分行列に対して判定してやるとO(N^6)になるが,これでもぎりぎり通る.(以下のコード)
オーダーを落とす方法としては,行の範囲は全探索するとして,列は始点のみ決めてやる.
市松模様になっている,とは,前の列と比べて,全てが一致するか,全てが反転していればOKなので,そうなってる範囲調べれば良い.
これで,列の終点のループが減ってO(N^5).
後は,列の始点も尺取メソッドで,一致しなかった場所まで一気に進めれば良いので,O(N^4).
全てが一致するか反転するか,というのは,ビット演算を使えばO(1)でできて,O(N^3).
だが…,O(N^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)

class ComplementMachine2D {
public:
int largestSubmatrix(vector <string> in) {
  int i,j,k,l;
  int x,y;
  int x1,x2,y1,y2;
  int res=0, area;
  int a[60], b[60], as, bs, m, dame;

  x = in.size();
  y = in[0].size();

  rep(i,x) rep(j,y) in[i][j] -= '0';

  rep(x1,x) REP(x2,x1,x) rep(y1,y) REP(y2,y1,y){
    area = (x2-x1+1) * (y2-y1+1);
    if(area <= res) continue;

    a[0] = x1;
    b[0] = y1;
    as = bs = 1;

    REP(i,x1+1,x2+1) if(in[i][y1]!=in[i-1][y1]) a[as++] = i;
    REP(i,y1+1,y2+1) if(in[x1][i]!=in[x1][i-1]) b[bs++] = i;

    a[as] = x2+1;
    b[bs] = y2+1;

    dame = 0;
    rep(i,as) if(!dame) rep(j,bs) if(!dame){
      m = (i+j)%2;
      m ^= in[x1][y1];

      REP(k,a[i],a[i+1]) if(!dame) REP(l,b[j],b[j+1]) if(!dame){
        if(in[k][l]!=m) dame=1;
      }
    }

    if(dame) continue;

    if(res < area) res = area;
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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