Ghost Legs [RUPC2018 Day2 F]

解法

https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day2/2751511

あみだくじはよく「順列から順列への写像」と考えることができる。
今回は縦線が3本なので、3!=6通りの順列の中での写像関数としてイメージできる。
各あみだくじにおいて、「012」「021」「102」「120」「201」「210」の6種類のどの写像になるかをまずは確かめよう。
それを使って「A[i] := i番目の写像の個数」を用意しておく。
　
あみだくじを通る前を「012」と考えると、あみだくじを1つ通ることで「012」～「210」へ遷移するような感じになる。
つまり、「012」-> ? -> ... -> 「012」となるようなパターンを探すことになる。
ここで同じ状態を2回通るのは無駄であるため、この様なパスの長さは高々7となる。
これは全探索できるので、全探索しよう。
全ての遷移について、どの写像を使っているかを調べて、使った写像の個数をカウントする。
この個数が、用意されているあみだくじの該当する写像の個数以下であれば実現可能である。

int N, A[6];
//---------------------------------------------------------------------------------------------------
vector<vector<int>> B = { {0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0} };
int get(vector<int> v) {
    rep(i, 0, 6) {
        int ok = 1;
        rep(j, 0, 3) if (v[j] != B[i][j]) ok = 0;
        if (ok) return i;
    }
    assert(0);
}
//---------------------------------------------------------------------------------------------------
#define yes "yes"
#define no "no"
string solve() {
    vector<int> v;
    v.push_back(0);
    rep(i, 0, 6) v.push_back(i);

    do {
        int s = 0, t = -1;
        rep(i, 1, 7) if (v[i] == 0) t = i;
        assert(1 <= t);

        vector<int> cnt(6);
        rep(i, s, t) {
            int a = v[i];
            int b = v[i + 1];

            vector<int> w;
            rep(u, 0, 3) rep(v, 0, 3) if (B[a][u] == B[b][v]) w.push_back(v);
            cnt[get(w)]++;
        }

        int ok = 1;
        rep(i, 0, 6) if (cnt[i] > A[i]) ok = 0;
        if (ok) {
            return yes;
        }
    } while (next_permutation(all(v)));

    return no;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        int w; cin >> w;
        vector<int> v = { 0, 1, 2 };
        rep(j, 0, w) {
            int a; cin >> a;
            if (a == 0) swap(v[0], v[1]);
            else swap(v[1], v[2]);
        }

        A[get(v)]++;
    }

    cout << solve() << endl;
}