最近解いた問題（AOJ)

　最近更新してなかったので適当にまとめ。
　2332 時空のスゴロクロード
　http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2332
　BFSで無限ループは特別に対処。こういうのいつもメモ化DFSして失敗してますね。苦手。

int N; int P[100010];
int next[100010];
bool vis[100010];
int dfs(int now) {
    if(vis[now]) return next[now] = -2;
    if(next[now] != -1) return next[now];
    vis[now] = true;
    return next[now] = P[now] == 0 ? now : dfs(now + P[now]);
}

int dist[100010]; 
int solve() {
    rep(i, N) dist[i] = INF; dist[0] = 0;
    queue<int> que; que.push(0);
    while(!que.empty()) {
        int now = que.front(); que.pop();
        if(now == N - 1) return dist[now];
        REP(i, 1, 7) {
            memset(vis, 0, sizeof(vis));
            int nxt = nx(min(now + i, N - 1));
            if(nxt == -2) continue;
            if(dist[nxt] != INF) continue;
            dist[nxt] = dist[now] + 1;
            que.push(nxt);
        }
    }
}
int main() {
    scanf("%d", &N);
    rep(i, N) scanf("%d", P + i);
    memset(next, -1, sizeof(next));
    printf("%d\n", solve());
    return 0;
}

　1238 True Liars
　http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1238
　面白い問題ですがこれは苦戦しましたね。
x is div, x is not divでN * 2の要素を持つUF木をつくってグルーピングした後にDPして復元。難易度600ですが本番で通すのはかなり厳しそうですね。
　DPと復元はあまり難しく感じなかったものの、上記のグルーピングがなかなか思いつきませんでした。こうすると対照なグループの組が二つずつ出来て、しかも根の番号がそれぞれhoge is divとhoge is not divになります。このうち片方だけ見て組み合わせDPして場合の数が1なら復元します。

struct UnionFind {
    vector<int> data;
    UnionFind(int N) : data(N, -1){}
    void unite(int x, int y) {
        x = root(x); y = root(y);
        if(x != y){
            data[x] += data[y];
            data[y] = x;
        }
    }
    int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]);}
    bool same(int a, int b) { return root(a) == root(b);}
};
int L[601], R[601];
int dp[601][301], from[601][301];
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, p1, p2;
    while(cin >> N >> p1 >> p2 && (N || p1 || p2)) {
        int P = p1 + p2;
        int x_, y_; string a_;
        UnionFind uf(P * 2);//node_i := if i % 2 (i / 2) is F else (i / 2) is T
        rep(i, N) {
            cin >> x_ >> y_ >> a_;
            --x_; --y_;
            if(a_ == "yes")
              uf.unite(x_ * 2, y_ * 2), uf.unite(x_ * 2 + 1, y_ * 2 + 1);
            else
              uf.unite(x_ * 2, y_ * 2 + 1), uf.unite(x_ * 2 + 1, y_ * 2);
        }
        memset(L, 0, sizeof(L)); memset(R, 0, sizeof(R));
        rep(i, P) {
            int par = uf.root(i * 2);
            if(par % 2) R[par / 2]++; else L[par / 2]++;
        }
        memset(dp, 0, sizeof(dp)); memset(from, 0, sizeof(from));
        int it = 0; dp[0][0] = 1;
        vector<int> group(P, 0);
        int curj; vector<bool> useR(P, false);
        auto upd = [](int& a, int b){
            if(b == 0) return false;
            a = min(2, a + b);
            return true;
        };
        rep(i, P) {
            if(L[i] == 0 && R[i] == 0) continue;
            if(L[i] == R[i]) goto fail;
            ++it; group[it] = i;
            rep(j, p1 + 1) {
                if(upd(dp[it][j + L[i]], dp[it - 1][j]))
                  from[it][j + L[i]] = j;
                if(upd(dp[it][j + R[i]], dp[it - 1][j]))
                  from[it][j + R[i]] = j;
            }
        }
        if(dp[it][p1] != 1) goto fail;
        curj = p1;
        for(int i = it; i >= 1; --i) {
            int temp = curj - from[i][curj];
            if(temp == R[group[i]]) useR[group[i]]= true;
            curj -= temp;
        }
        rep(i, P) {
            int par = uf.root(i * 2);
            if((par % 2 && useR[par / 2]) || (par % 2 == 0 && !useR[par / 2]))
              cout << i + 1 << endl;
        }
        cout << "end" << endl;
        continue;
      fail:
        cout << "no" << endl;
    }
    return 0;
}

　1330 Never Wait for Weights
　http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1330
　引き続きUnionFindTreeで解ける問題。UF木を使う問題はクイズみたいで面白い問題やグラフっぽい問題など幅が広く面白いですね。これはクエリに答える感じの問題。
　物体xとyの重量差について、質問か答えるかの二種類のクエリを処理します。なんと面白いことに重さをUF木で根までの距離として持たせておくと簡単に解けます。常に軽い方が親になるように併合し、併合時には旧親-新親の距離だけを確定させておき、経路圧縮時に親の方からあるノードの親までの距離を確定させていきます。親の方からやるのは経路圧縮を同時に2回以上行う場合のためです。

struct UnionFind {
    vector<int> data;
    vector<ll> rootd;//rootd[i] : dist from node[i] to node[root(i)]
    UnionFind(int N) : data(N, -1), rootd(N, 0) {}
    void unite(int x_, int y_, ll weight) {
        int x = root(x_), y = root(y_);
        if(x != y){
            data[x] += data[y];
            data[y] = x;
            rootd[y] = weight - rootd[y_] + rootd[x_];
        }
    }
    int root(int x) {
        vector<int> memo;
        while(data[x] >= 0) {
            memo.push_back(x);
            x = data[x];
        }
        int res = x;
        for(int i = memo.size() - 1; i >= 0; --i) {
            int k = memo[i];
            rootd[k] += rootd[data[k]];
            data[k] = res;
        }
        return res;
    }
    ll dist(int a, int b) { return rootd[b] - rootd[a];}
    bool same(int a, int b) { return root(a) == root(b);}
};
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    while(cin >> N >> M && N) {
        UnionFind uf(N);
        char q; int a, b; ll w;
        rep(i, M) {
            cin >> q >> a >> b;
            --a; --b;
            if(q == '?') {
                if(uf.same(a, b)) cout << uf.dist(a, b) << '\n';
                else cout << "UNKNOWN" << '\n';;
            }else {
                cin >> w;
                uf.unite(a, b, w);
            }
        }
    }
    return 0;
}

　プロコンは楽しいですが最近始めたプログラミングのバイトはあまり楽しくないです。やっぱりラノベ作家とかになりたいですね。言うだけなら簡単なのですが。