ICPC国内予選2010

24位. 多分去年とあまり変わらない. まさに「まるで成長してない…」

前日夜中に体温が38度を突破. 一時は出場できないかと冷や汗をかいたが, 当日昼過ぎまで寝た結果, 体調が戻ったので参加することに. ちなみに私以外の2人はそれぞれ初対面なので, 出れて良かった.*1

開始後はA, Bを解いたあとCをメンバーにバトンタッチ. その後Dに取りかかるがバグが取りきれず終了. 実装力が足りないなぁと思う. 夏休みはちまちま問題を解いていきたい...

ちなみに以下は後日解いたD. 見直すとクズっぽさが半端無い. 下から適当にBFSでブロック探索(重心と下のブロックの情報も一緒に)→木を作成→再帰で計算 みたいな流れ. しかし本当長いなこのコード.................................

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

vector<vector<int> > lnk;

struct Node {
    int x, y, c;
    int  xl, xr;
    Node(int x, int y, int c, int xl, int xr) : x(x), y(y), c(c), xl(xl), xr(xr) {}
};

struct SPoint {
    int x, y, p, pn;
    SPoint(int x, int y, int p, int pn) : x(x), y(y), p(p), pn(pn) {}
};

struct Piece {
    int n;
    double x;
    int p;
    int xl, xr;
    Piece(int n, double x, int p, int xl, int xr) : n(n), x(x), p(p), xl(xl), xr(xr) {}
};

bool f(int);

vector<Piece> pieces;

int main(int argc, char *argv[])
{
    bool visited[60][10];
    int w, h, m[60][10];
    char c;
    while (scanf("%d %d ", &w, &h), w|h) {
        memset(visited, false, sizeof(visited));

        // reading
        for (int i=h-1; i>=0; --i) {
            for (int j=0; j<w; ++j) {
                scanf("%c ", &c);
                if (c == '.') {
                    m[i][j] = 0;
                } else {
                    m[i][j] = c - '0';
                }
                visited[i][j] = false;
            }
        }

        // search starting point
        int sx, sy = 0;
        for (int i=0; i<w; ++i) {
            if (m[0][i]) {
                sx = i;
                sy = 0;
                break;
            }
        }

        pieces.clear();
        lnk.clear();


        queue<SPoint> SQ;
        SQ.push(SPoint(sx, sy, -1, -1));
        int pn = 0;
        while (!SQ.empty()) {
            SPoint sp = SQ.front();
            SQ.pop();
            if (visited[sp.y][sp.x]) {
                continue;
            }

            double gx = 0;
            queue<Node> NQ;
            NQ.push(Node(sp.x, sp.y, m[sp.y][sp.x], sp.x, sp.x+1));
            int xl = sp.x, xr = sp.x+1;
            while (!NQ.empty()) {
                Node n = NQ.front();
                NQ.pop();
                if (visited[n.y][n.x]) {
                    continue;
                }

                visited[n.y][n.x] = true;
                gx += n.x + 0.5;

                if (n.y+1 < h && m[n.y+1][n.x] != n.c &&
                    !visited[n.y+1][n.x] && m[n.y+1][n.x]) {
                    SQ.push(SPoint(n.x, n.y+1, sp.p, pn));
                }

                if (n.y-1 >= 0 && m[n.y-1][n.x] &&
                    m[n.y][n.x] != m[n.y-1][n.x]) {
                        xl = min(xl, n.x);
                        xr = max(xr, n.x+1);
                }

                for (int i=0; i<4; ++i) {
                    int nx = n.x + dx[i];
                    int ny = n.y + dy[i];
                    if (nx < 0 || nx >= w || ny < 0 || ny >= h ||
                        visited[ny][nx] || m[ny][nx] != n.c) {
                        continue;
                    }
                    NQ.push(Node(nx, ny, n.c, xl, xr));
                }
            }
            gx /= 4.0;
            pieces.push_back(Piece(1, gx, sp.pn, xl, xr));
            ++pn;
        }

        bool onGround = false;
        for (int i=0; i<w; ++i) {
            if (m[0][i] && !onGround) {
                pieces[0].xl = i;
                onGround = true;
            } else if (onGround && !m[0][i]) {
                pieces[0].xr = i;
                break;
            } else if (onGround && i == w-1) {
                pieces[0].xr = i+1;
            }
        }

        lnk.clear();
        lnk.resize(pieces.size());

        for (int i=0; i<(int)pieces.size(); ++i) {
            if (pieces[i].p >= 0) {
                lnk[pieces[i].p].push_back(i);
            }
        }
        if (f(0)) {
            printf("STABLE\n");
        } else {
            printf("UNSTABLE\n");
        }
    }
    return 0;
}

bool f(int i) {
    Piece p = pieces[i];
    int xl =p.xl;
    int xr = p.xr;
    if (lnk[i].size() == 0) {
        return xl < p.x && p.x < xr;
    }

    int j, n = 0;
    double x = 0, gx=0;
    bool ret = true;
    for (j=0; j<(int)lnk[i].size(); ++j) {
        ret = ret && f(lnk[i][j]);
        n += pieces[lnk[i][j]].n;
        x += pieces[lnk[i][j]].x;
        gx += pieces[lnk[i][j]].x*pieces[lnk[i][j]].n;
    }
    pieces[i].x = (gx+pieces[i].x)/(n+1);
    pieces[i].n = n+1;
    return ret && xl < pieces[i].x && pieces[i].x < xr;
}

ほ、本番の時に焦ったやつを直した…とは言え酷いにも程がある--); 精進したい

*1:この時点で突っ込み所満載のチームである