Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-05-05

[][] SRM 505 Div1 300 RectangleArea 01:38 はてなブックマーク -  SRM 505 Div1 300 RectangleArea - 練習帳

 前回のSRMのEasyがwriterさんのコードを見てようやく理解できたので,備忘録としてメモを残しておこうと思います.

300 RectangleArea

要約

 N*Mの小長方形に分割された長方形があり,小長方形のうちいくつかは面積がわかっている.あといくつ小長方形の面積がわかれば全体の面積が求まるか.個数の最小値を求めよ.N, Mは1以上50以下.


方針

 下図のように4つの小長方形がつくる長方形を,便宜的に中長方形呼ぶ事にします.

□□□□□□□□□□
□■□□□■□□□□
□□□□□□□□□□
□■□□□■□□□□
□□□□□□□□□□
(中長方形の例)

中長方形が退化して,4頂点がすべて同じ小長方形を指している場合も中長方形と考えます.

 まずサンプルケースを見ると,中長方形を作る小長方形4つのうち,3つの面積が既知ならば残り一つの面積も計算できる事がわかります.そこでまず,初期状態から新たに情報を追加しなくても面積が求まる部分を出来る限り求めてみます.

#include <string>
#include <vector>
#include <sstream>
#include <iostream>

using namespace std;

vector<string> k;

bool check(int i, int ii, int j, int jj){
  int cnt = 0;
  if(k[i][j] == 'Y') cnt++;
  if(k[ii][j] == 'Y') cnt++;
  if(k[i][jj] == 'Y') cnt++;
  if(k[ii][jj] == 'Y') cnt++;
  if(cnt == 3){
    k[i][j] =  k[ii][j] =  k[i][jj] =  k[ii][jj] = 'Y';
    return true;
  }else{
    return false;
  }
}


class RectangleArea {
public:
  int minimumQueries(vector <string> known) {
    k = known;
    int n = known.size();
    int m = known[0].size();
    bool flag = true;
    while(flag){
      flag = false;
      for(int i = 0;i<n;i++){
	for(int ii = i;ii<n;ii++){
	  for(int j = 0;j<m;j++){
	    for(int jj = j;jj<m;jj++){
	      if(check(i, ii, j, jj)){
		flag = true;
	      }
	    }
	  }
	}
      }
    }
    // COMPLEMENT FINISHED 
  }
};

コメントの部分に達すると,長方形内のどの中長方形も「4頂点すべて面積既知」or「すべて面積未知」となります.例えば典型的には下図のような状況です.(■,●は面積既知,□は未知).

□□□□■□□■□■
□●□●□●□□□□
□□□□■□□■□■ 
□●□●□●□□□□
□□□□■□□■□■
□□□□□□□□□□
(初期状態から面積がわかるものを全て補完した状態の例)

この場合,面積既知の小長方形を●のグループと■のグループとで分ける事が出来ます.なんとなくそれっぽい感じはするのですが,それをきちんと言葉で表すと,「どの●を取っても,その●から上下左右に小長方形を走査すると●しか見つからず,■は見つからない」という状態です.これは行と列を適当に入れ替えると分かりやすくなります.

■■■□□□□□□□
■■■□□□□□□□
■■■□□□□□□□ 
□□□●●●□□□□
□□□●●●□□□□
□□□□□□□□□□
(直前の図の行同士,列同士を適当に入れ替えた)

ここから適当に小長方形を一つ選べば●のグループと■のグループを「繋げる」ことが出来ます.例えば上から3行目(■のある行)と左から4列目(●のある列)の交点上にある小長方形を選ぶと,面積の分かる部分は下図のように増えます.

■■■■■□□□□□
■■■■■□□□□□
■■■■■□□□□□ 
■■■■■□□□□□
■■■■■□□□□□
□□□□□□□□□□
(一つ面積のわかる部分を付け加えてた結果,面積の分かる部分)

つまり,(グループの数)- 1個の小長方形を付け加えればこれらのグループはひとまとまりに出来ます.残りの白部分の面積を全て求めるには(白行の数)+(白列の数)個の小長方形の面積が分かれば十分です.

■■■■■■■■■■
■■■■■□□□□□
■■■■■□□□□□ 
■■■■■□□□□□
■■■■■□□□□□
■□□□□□□□□□
(残りの小長方形の面積を知るためにいくつか■の長方形を追加)

 残っている問題は次の2つです.

  • 面積既知の小長方形をグループ分けした時のグループの数は?
  • グループをひとつにまとめ上げた後に残っている白行,白列の数は?

グループ分け,ということでunion-findが使う方法を使います.ここでは小長方形ではなく行,列のグループ分けするとうまく行きます(グループ分けを行,列に対して行おうという発想が自分にはありませんでした.).小長方形のグループを上下左右に延ばして「行と列の集合」に変換します.例えば

□□□□■□□■□■
□□□□□□□□□□
□□□□■□□■□■ 
□□□□□□□□□□
□□□□■□□■□■

なら

■■■■■■■■■■
□□□□■□□■□■
■■■■■■■■■■ 
□□□□■□□■□■
■■■■■■■■■■

に変換します(逆の操作も可能です).

すると「「要」となる小長方形があるなら,小長方形が属する列と属する行は同じグループに属する」とルール化できます.

以上をまとめて,次のような下のようなコードが出来ました.

コード例
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <set>
#include "../print.hpp"

using namespace std;

class UnionFind{
public:
  UnionFind(int _n):n(_n){
    par.resize(n);
    for(int i = 0;i<n;i++){
      par[i] = i;
    }
    rank.resize(n, 0);
  }

  int find(int x){
    if(par[x] == x){
      return x;
    }else{
      return par[x] = find(par[x]);
    }
  }

  void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return ;
    if(rank[x] < rank[y]){
      par[x] = y;
    }else{
      par[y] = x;
    }
    if(rank[x] == rank[y]) rank[x]++;
  }
  bool same(int x, int y){
    return find(x) == find(y);
  }

private:
  int n;
  vector<int> par;
  vector<int> rank;
};


vector<string> k;

bool check(int i, int ii, int j, int jj){
  int cnt = 0;
  if(k[i][j] == 'Y') cnt++;
  if(k[ii][j] == 'Y') cnt++;
  if(k[i][jj] == 'Y') cnt++;
  if(k[ii][jj] == 'Y') cnt++;
  if(cnt == 3){
    k[i][j] =  k[ii][j] =  k[i][jj] =  k[ii][jj] = 'Y';
    return true;
  }else{
    return false;
  }
}

class RectangleArea {
public:
  int minimumQueries(vector <string> known) {
    k = known;
    int n = known.size();
    int m = known[0].size();


    // In fact, this part is redundant. See also the remark below.
    bool flag = true;
    while(flag){
      flag = false;
      for(int i = 0; i < n; i++){
	for(int ii = i; ii < n; ii++){
	  for(int j = 0; j < m; j++){
	    for(int jj = 0; jj < m; jj++){
	      if(check(i, ii, j, jj)){
		flag = true;
	      }
	    }
	  }
	}
      }
    }
    ///////////////////////////


    UnionFind uf(n + m);
    for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
	if(k[i][j] == 'Y'){
	  uf.unite(i, j + n);
	}
	  
      }
    }
    int ans = 0;
    for(int i = 0; i < n + m; i++){
      if(uf.find(i) == i){
	ans ++ ;
      }
    }
    return ans - 1;
  }
};

分析

 実は,上の小長方形を補完する部分は余分です.例えば行と列をつなぐ要を

□□□□■□□■□■
□□□□□□□□□□
□□□□■□□■□■ 
□□□□□□□□□□
□□□□■□□■□■

からいくつか減らして

□□□□■□□■□□
□□□□□□□□□□
□□□□□□□□□■ 
□□□□□□□□□□
□□□□□□□■□■

としても,同じ行,列のグループを作ります.