ICPC 国内予選2010D ぐらぐら AOJ1168

解説（文章にするのがめんどくさいので箇条書きで書きます）

• 最初の入力では数字が1~9の範囲しかなく、ピースが10個以上の時に区別が難しいのでO(WH)で番号を振りなおす。（これによってピースが合計何個あるのかもわかる）

• 次にそれぞれのピースについて、下に接するブロックの右端の座標(XL)、左端の座標(XR)、重さの総和、下には何番目のピースがあるのか（これはvectorに保存しておく）を求め、それぞれ配列に保存する

• 最後にそれぞれのピースについてSTABLEかどうかを確認していき、一つでのUNSTABLEなピースがあればUNSTABLEとすればよい。具体的にどう確認するかというと、再帰（深さ優先探索）で自分の上にあるピースの重さの総和とブロックの数の総和をもとめそれらの数値から重心のx座標をもとめそれをXL、XRと比較すればよい。

解法は自明なのだがそれを時間内にミスなく実装するとなるとなかなか難しいので経験の差が出てくる問題なのかもしれない。

#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

typedef pair<double, int> PD;

 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

bool ch[65][15];
int num[65][15];
int w,h;
double wei[160];
int x[160][2]; // 0:Xl,1:Xr
vector<int> v[160];



void find(int x,int y,int count){
    int sum = 1;
    queue<P> que;
    que.push(P(x,y));
    while(!que.empty()){
        if(sum == 4)break;
        P q = que.front(); que.pop();
        for(int k = 0;k < 4;k++){
            int nx = q.fs + dx[k],ny = q.sc + dy[k];
            if(nx < 0 || ny < 0 || nx >= h || ny >= w)continue;
            if(ch[nx][ny] == false && num[x][y] == num[nx][ny]){
                sum++;
                ch[nx][ny] = true;
                num[nx][ny] = count;
                que.push(P(nx,ny));
            }
        }
    }
}

PD get_weight(int k){
    double wsum = wei[k];
    int sec = 4;
    for(int i = 0;i < v[k].size();i++){
        PD p = get_weight(v[k][i]);
        wsum += p.fs;
        sec += p.sc;
    }
    return (PD(wsum,sec));
}

int main(){
    while(true){
        cin >> w >> h;
        if(w == 0)break;
        for(int i = 0;i < h;i++){
            char tmp[20];
            cin >> tmp;
            for(int j = 0;j < w;j++){
                ch[i][j] = false;
                if(tmp[j] == '.'){
                    num[i][j] = 0;
                    ch[i][j] = true;
                }else{
                    num[i][j] = tmp[j] - '0';
                }
            }
        }
        for(int j = 0;j < w;j++) num[h][j] = 0;
        int count = 0;
        for(int i = 0;i < h;i++){
            for(int j = 0;j < w;j++){
                if(ch[i][j] == false){
                    ch[i][j] = true;
                    count++;
                    find(i,j,count);
                    num[i][j] = count;
                }
            }
        }

        for(int k = 1;k <= count;k++){
            wei[k] = 0.0;
            int und=0;
            int a=100,b=-1;
            for(int i = 0;i < h;i++){
                for(int j = 0;j < w;j++){
                    if(num[i][j] != k) continue;
                    wei[k] += (double) j + 0.5;
                    if((num[i+1][j] >= 1 && num[i+1][j] != k) || i == h-1){
                        und = num[i+1][j];
                        a = min(a,j);
                        b = max(b,j+1); 
                    }
                }
            }
            v[und].push_back(k);
            x[k][0] = a;
            x[k][1] = b;
        }
        bool ans = true;
        for(int i = 1;i <= count;i++){
            PD p = get_weight(i);
            if(x[i][0] >= p.fs/(double)p.sc || x[i][1] <= p.fs/(double)p.sc){
                ans = false;
                break;
            }
        }
        if(ans){
            cout << "STABLE" << endl;
        }else{
            cout << "UNSTABLE" << endl;
        }
        for(int i = 0;i <= count;i++)  v[i].clear();
    }
}