ICPC国内予選2020 D問題：icpca 文字

問題. Icpca 文字

$n$ 種類の相異なる英大文字からなる文字列 $a_1 a_2 \ldots a_n$ と、式 $S, T$ が与えられる。
式 $S, T$ は次の文法規則からなる。
　・E $::=$ F | '(' E '<' E ')' | '(' E '>' E ')'
　・F $::= a_1$ | $a_2$ | $\ldots$ | $a_n$
ただし、不等式の評価は $a_i < a_j$ ならば $\min\{a_i, a_j\}$ 、 $a_i > a_j$ ならば $\max\{a_i, a_j\}$ とする。
$a_1 a_2 \ldots a_n$ 上の全順序のうち式 $S$ と $T$ の値が等しくなるものの数を求めよ。

制約： $1 \le n \le 16$ 、 $0 \le |S|, |T| \le 100$

解法．

$a_1 a_2 \ldots a_n$ 上の全順序は $n!$ 通りあるので全順序を全列挙して式 $S, T$ を評価するという方針では間に合いません。そこで、式 $S$ と $T$ の値が $a_i$ となる全順序が何通りあるのかを求めることを考えます。

下の式の構文木で $a_i$ を A として考察します。A が式の値となるためには A となる葉の少なくともひとつが、その葉から根までの経路の評価で勝ち続ける必要があります。例えば NWEAS という全順序を考えたときには左にある A が勝ち続けるので、全順序 NWEAS に対する式の値は A となります。また、A よりも小さい要素を並び替えた WENAS や WNEAS なども式の値は A となります。

　　　　　 f:id:tatanaideyo:20210924071302p:plain:w250

ここで、A よりも小さい要素と大きい要素の集合をそれぞれ $L, R$ とします（上の例では $L = \{N, W, E\}, R = \{S\}$ ）。 $L, R$ 内の要素の順序が異なるどの全順序に対しても式の値が A となるかどうかは変わりません。なぜならば、式の値が A かどうかが変わるということは、A を葉とする頂点から根までの経路中に評価が反転する頂点があるということになります。しかし、木の高さによる帰納法から $L, R$ 内の要素の順序を変えただけでは評価が反転することがないことが分かります。
また、 $L, R$ が固定されたときの式の値は $O(|L| + |R|)$ 時間で求めることができ、そのときの全順序の種類数は $|L|! \times |R|!$ となることが分かります。 $L, R$ の選び方は $2^{n - 1}$ 通りあるので、各 $a_i$ に対して $a_i$ よりも小さい要素と大きい集合を全探索して式の値を評価しても間に合います。

計算時間： $O\left( n \, 2^{n - 1} \times (|S| + |T|)\right)$

ソースコードを表示

#include <iostream>
#include <vector>

using namespace std;

using ll = long long;

class IcpcanAlphabet {
public:
    explicit IcpcanAlphabet(const int max_n) : fact(max_n + 1), cmp(26) {
        fact[0] = 1;
        for (int i = 1; i <= max_n; ++i) fact[i] = i * fact[i - 1];
    }

    ll GetNumTotalOrderEqualExp(const std::string &A, const std::string &S, const std::string &T) {
        const int N = A.size();
        ll num = 0;
        for (int i = 0; i < N; ++i) { // S と T の値が A_i となる全順序の数を求める
            cmp[index(A[i])] = 0;

            const unsigned int univ = ((1 << N) - 1) ^ (1 << i); // univ = {0, 1, ..., N - 1} / {i}
            unsigned int sub = univ;
            while (true) { // univ の部分集合を全列挙する：部分集合 sub := {x \in univ | x < i} とする
                int num_less = 0;
                for (int j = 0; j < N; ++j) {
                    if (sub >> j & 1) {
                        ++num_less;
                        cmp[index(A[j])] = -1;
                    }
                    else if (i != j) {
                        cmp[index(A[j])] = 1;
                    }
                }

                auto it_s = S.begin(), it_t = T.begin();
                if (Evaluate(it_s) == 0 && Evaluate(it_t) == 0)
                    num += fact[num_less] * fact[N - num_less - 1];

                if (sub == 0)  break; // 部分集合が空の場合も計算できるように
                sub = (sub - 1) & univ;
            }
        }

        return num;
    }

private:
    std::vector<ll> fact;
    // 固定された a \in A に対して a' \in A の cmp の値を a との大小関係で定める
    // a == a' なら cmp[index(a')] = 0
    // a < a'   なら cmp[index(a')] = 1
    // a > a'   なら cmp[index(a')] = -1
    std::vector<int> cmp;

    unsigned index(const char c) const { return static_cast<unsigned>(c - 'A'); }

    int Evaluate(std::string::const_iterator& it) {
        // E ::= F | '(' E '<' E ')' | '(' E '>' E ')'
        if (*it == '(') {
            int lhs = Evaluate(++it);
            char op = *it;
            int rhs = Evaluate(++it);
            ++it; // skip ')'
            return (op == '<') ? std::min(lhs, rhs) : std::max(lhs, rhs);
        }
        else {
            return cmp[index(*it++)];
        }
    }
};

int main() {
    const int MAX_N = 16;
    IcpcanAlphabet solver(MAX_N);

    int n;
    while (std::cin >> n, n) {
        std::string a, s, t;
        std::cin >> a >> s >> t;
        std::cout << solver.GetNumTotalOrderEqualExp(a, s, t) << std::endl;
    }

    return 0;
}

競プロから遠ざかっていたので大変だった。コンテスト時間内で解いている人スゴイな。