AOJ 1238 True Liars

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1238

解法

人をノードと見て，x y a を辺と考えると良い．ある人を仮に divine あるいは delivish と定めると，その人と関係のある人間の性質が一意に定まる．
よって，関係のあるグループについて2通りを試して，その結果で dp をすればよい．
・dp[i][j][k] := i 番目のグループまで見て，divine が j 人であり，delivish が k 人である時の，直前のグループの状態
とする．直前のグループの状態は，代表の id と，その人の性質，そしてそのグループの分配の仕方を表す．
同じ dp[i][j][k] に到達する状態が複数あった場合，以降その状態とそこから遷移できるすべての状態を ambiguous に設定してしまう．
最後に dp.back()[p1][p2] が有効なら復元していく．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

struct edge {
    int to;
    bool yes;
};

using edges = vector<edge>;
using graph = vector<edges>;

// (divine, devilish)
pii dfs(graph const& g, int v, bool divine, vector<bool>& checked) {
    auto res = make_pair((int)divine, (int)!divine);
    checked[v] = true;
    for(auto& e : g[v]) {
        if(checked[e.to]) {
            continue;
        }
        bool next_state = (divine && e.yes || !divine && !e.yes);
        auto t = dfs(g, e.to, next_state, checked);
        res.first += t.first;
        res.second += t.second;
    }
    return res;
}

void determine(graph const& g, int v, bool divine, vector<int>& res) {
    res[v] = divine;
    for(auto& e : g[v]) {
        if(res[e.to] != -1) {
            continue;
        }
        bool next_state = (divine && e.yes || !divine && !e.yes);
        determine(g, e.to, next_state, res);
    }
}

struct data {
    int person_id;
    bool divine;
    pii each_num; // (divine, devilish)
    data() : person_id(-1), divine(false), each_num(make_pair(0, 0))
    {}
};

int main() {
    int n, p1, p2;
    while(cin >> n >> p1 >> p2, n || p1 || p2) {
        graph g(p1 + p2);
        if(n == 0) {
            if(p2 == 0) {
                for(int i = 1; i <= p1 + p2; ++i) {
                    cout << i << endl;
                }
            } else if(p1 != 0) {
                cout << "no" << endl;
                continue;
            }
            cout << "end" << endl;
            continue;
        }
        for(int i = 0; i < n; ++i) {
            int x, y;
            string a;
            cin >> x >> y >> a;
            g[x - 1].push_back(edge{y - 1, a == "yes"});
            g[y - 1].push_back(edge{x - 1, a == "yes"});
        }
        vector<vector<vector<data>>> dp(1, vector<vector<data>>(p1 + 1, vector<data>(p2 + 1)));
        dp[0][0][0].person_id = 0;
        vector<bool> checked(p1 + p2);
        for(int i = 0; i < p1 + p2; ++i) {
            auto now = dp.back();
            vector<vector<data>> nxt(p1 + 1, vector<data>(p2 + 1));
            if(!checked[i]) {
                for(int b = 0; b <= 1; ++b) {
                    data d;
                    d.person_id = i;
                    d.divine = b;
                    auto checked2 = checked;
                    d.each_num = dfs(g, i, b, checked);
                    if(b == 0) {
                        checked = checked2; // restore
                    }
                    for(int j = 0; j <= p1; ++j) {
                        for(int k = 0; k <= p2; ++k) {
                            if(now[j][k].person_id == -1) {
                                continue;
                            }
                            int nj = j + d.each_num.first, nk = k + d.each_num.second;
                            if(nj > p1 || nk > p2 || nxt[nj][nk].person_id == -2) {
                                continue;
                            }
                            if(nxt[nj][nk].person_id >= 0 || now[j][k].person_id == -2) { // ambiguous
                                nxt[nj][nk].person_id = -2;
                                continue;
                            }
                            nxt[nj][nk] = d;
                        }
                    }
                }
                dp.push_back(move(nxt));
            }
        }
        auto now = dp.back()[p1][p2];
        if(now.person_id < 0) {
            cout << "no" << endl;
        } else {
            vector<int> res(p1 + p2, -1);
            int P1 = p1, P2 = p2;
            for(int i = dp.size() - 1; i > 0; --i) {
                auto d = dp[i][P1][P2];
                determine(g, d.person_id, d.divine, res);
                P1 -= d.each_num.first;
                P2 -= d.each_num.second;
            }
            for(int i = 0; i < p1 + p2; ++i) {
                if(res[i] == 1) {
                    cout << i + 1 << endl;
                }
            }
            cout << "end" << endl;
        }
    }
}

感想

まあすぐわかると思うんですが，実装方針が良くないです．特に，dp[i][j][k] としているのが悪くて，j の値がわかれば k の値は自動的に決まるため，片方を保つ必要はありません．実装方針どころか，計算量が変わるので非常にまずいです．（今回は十分間に合いますけどね．）
また，ambiguous な状態の表現は，そうなる遷移の数を dp の値として持つことで自然に表現できるため，変な負の値を割り当てずにそうすべきだったかな．
あとは data 構造体で持つのではなく，複数の配列に分けて持ったほうがきれいかもしれない．これは好みかな？