SRM505 Div1 Easy(300), Div2 Hard(900) RectangleArea

RectangleArea

Div2だと900。このパターンは初めて見た。

R0を決めると全てのRi,Cjが定まるとき、RiはR0に比例しCjはR0に反比例するので打ち消し合って面積が求められる。
どれか１つを決めると他が定まるRi,Cjを１つの組として、グループ分けする。あるRiとCjが同じ組になるのはAijが既知である場合。組の個数をcとすると、任意の組２つは適切な問い１回で同じ組にできるし、１回の問いで３つ以上の組を纏めることはできないので、c-1が答。

#include <vector>
#include <string>
using namespace std;

//  Union-Find木
class UnionFind
{
    vector<int>p,r;
public:
    UnionFind(int n):p(n,-1),r(n){}
    int find(int x){return p[x]>=0?p[x]=find(p[x]):x;}
    void unite(int x,int y){x=find(x),y=find(y);
        if(x!=y)if(r[x]<r[y])p[x]=y;else p[y]=x,r[x]+=r[x]==r[y];}
    bool same(int x, int y){return find(x)==find(y);}
    bool root(int x){return x==find(x);}
};

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

    UnionFind u(N+M);

    for ( int i=0; i<N; i++ )
    for ( int j=0; j<M; j++ )
        if ( known[j][i]=='Y' )
            u.unite(i,N+j);

    int c = 0;
    for ( int i=0; i<N+M; i++ )
        if ( u.root(i) )
            c++;
    return c-1;
}};