2023-10-27

TTPC 2023 F - N^a (log N)^b

AtCoder 有志コン TTPC 構文解析文字列 BNF 構文解析:再帰下降パーサ

この問題のおかげで、構文解析力が上がった！

問題へのリンク

問題概要

次のように、 $N$ の関数を表す式 $F(N)$ が与えられる。基本的には「+」「*」「^」「log」で構成されるものである。

N*log(N^2)*log(N)+N+log(N^1+N)^2*N

より正確には、次の BNF によって定義されるような文字列 $S$ が与えられる。

<expr> ::= <term> | <expr> "+" <term>
<term> ::= <factor> | <term> "*" <factor>
<factor> ::= "N" | "N^" <number> | "log(" <expr> ")" | "log(" <expr> ")^" <number> | "(" <expr> ")"
<number> ::= <non_zero_digit> | <non_zero_digit> <digit_string>
<digit_string> ::= <digit> | <digit> <digit_string>
<non_zero_digit> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<digit> ::= "0" | <non_zero_digit>

この関数 $F(N)$ について、

$\displaystyle \lim_{N \to \infty}\frac{F(N)}{N^{a}(\log N)^{b}}$

の値が有限値に収束するような非負整数の組 $(a, b)$ の辞書順最小の値を答えよ。

制約

$1 \le |S| \le 10^{5}$

考えたこと

ランダウの $O$ 記法にとてもよく似ていると思った。基本的には、ノード状態は

$N^{x} (\log N)^{y}$ を表す値 $x, y$
数値 $z$ を表す値 $z$

をマージして、3 つの値の組 $(x, y, z)$ で表すことにして、

"+"：状態 $(x, y)$ についての辞書順最大値を選ぶ
"*"：状態 $(x, y)$ についてのペア和をとる
"^"：状態 $(x, y)$ に対して状態 $z$ の演算を実行した結果は $(xz, yz)$ になる

というようにすれば良いと考えた。

しかし、"log" をとる操作について考えると....."log(log(N))" のようなものが怪しく思えてくる。このような項があるとき、最終結果において

$\displaystyle \lim_{N \to \infty}\frac{F(N)}{N^{a}(\log N)^{b}}$

を有限値にするための $b$ の値が 1 増える。よって、最終的には次のように表すことにした。

$N^{x} (\log N)^{y}$ の形の場合： $(x, y, false, 1)$
$N^{x} (\log N)^{y} (\log N より小さい項)$ の形の場合： $(x, y, true, 0)$
数値 $z$ を表す値 $(0, 0, false, z)$

この 4 つ組の状態に対して、「+」「*」「^」「log」を定義することで AC となった。

コード

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


// Parser
template<class T> struct Parser {
    /* settings */
    vector<set<char>> OPERATORS;              // operator priority
    function<T(char, T, T)> OP;               // binary operation
    function<T(const string&, int&)> GETNUM;  // number parser
    
    /* advanced settings */
    string OPERATOR_FUNC;                     // implies inner function
    function<T(T)> FUNC;                      // inner function in the string
    
    /* results */
    string S;
    int root;                    // vals[root] is the answer
    vector<T> vals;              // value of each node
    vector<char> ops;            // operator of each node
    vector<int> left, right;     // the index of left-node, right-node
    vector<int> ids;             // the node-index of i-th value
    
    /* constructor */
    Parser() {}
    Parser(const vector<set<char>> &operators,
           const function<T(char, T, T)> op,
           const function<T(const string&, int&)> getnum) {
        init(operators, op, getnum);
    }
    Parser(const vector<set<char>> &operators,
           function<T(char, T, T)> op,
           const function<T(const string&, int&)> getnum,
           const string &operator_func,
           const function<T(T)> func) {
        init(operators, op, getnum, operator_func, func);
    }
    void init(const vector<set<char>> &operators,
              const function<T(char, T, T)> op,
              const function<T(const string&, int&)> getnum) {
        OPERATORS = operators;
        OP = op;
        GETNUM = getnum;
    }
    void init(const vector<set<char>> &operators,
              const function<T(char, T, T)> op,
              const function<T(const string&, int&)> getnum,
              const string &operator_func,
              const function<T(T)> func) {
        OPERATORS = operators;
        OP = op;
        GETNUM = getnum;
        OPERATOR_FUNC = operator_func;
        FUNC = func;
    }
    void clear() {
        S = "";
        vals.clear(), ops.clear(), left.clear(), right.clear(), ids.clear();
    }
    
    /* main parser */
    T parse(const string &str) {
        clear();
        S = str;
        int p = 0, id = 0;
        root = parse(p, id);
        return vals[root];
    }
    int parse(int &p, int &id, int depth = 0) {
        if (depth < (int)OPERATORS.size()) {
            int lp = parse(p, id, depth + 1);
            while (p < (int)S.size() &&
                   OPERATORS[(int)OPERATORS.size() - depth - 1].count(S[p])) {
                char op = S[p++];
                int rp = parse(p, id, depth + 1);
                lp = new_node_with_left_right(op, lp, rp);
            }
            return lp;
        } else if (S[p] == '(') {
            ++p;                                 // skip "("
            int lp = parse(p, id, 0);
            ++p;                                 // skip ")"
            return lp;
        } else if (S.substr(p, OPERATOR_FUNC.size()) == OPERATOR_FUNC) {
            p += (int)OPERATOR_FUNC.size() + 1;  // skip "OPERATOR_FUNC("
            int lp = parse(p, id, 0);
            ++p;                                 // skip ")"
            return new_node_with_left(lp);
        } else {
            return new_leaf(p, id);
        }
    }
    
    /* generate node */
    // value
    int new_leaf(int &p, int &id) {
        vals.push_back(GETNUM(S, p));
        ops.push_back('n');
        left.push_back(-1);
        right.push_back(-1);
        ids.push_back(id++);
        return (int)vals.size() - 1;
    }
    // FUNC(lp)
    int new_node_with_left(int lp) {
        vals.push_back(FUNC(vals[lp]));
        ops.push_back('f');
        left.push_back(lp);
        right.push_back(-1);
        ids.push_back(-1);
        return (int)vals.size() - 1;
    }
    // (lp) op (rp)
    int new_node_with_left_right(char op, int lp, int rp) {
        vals.push_back(OP(op, vals[lp], vals[rp]));
        ops.push_back(op);
        left.push_back(lp);
        right.push_back(rp);
        ids.push_back(-1);
        return (int)vals.size() - 1;
    }
    
    /* dump */
    void dump() {
        dump_rec(root);
    }
    void dump_rec(int v, string space = "") {
        cout << space << v << ": (" << ops[v] << ", " << vals[v]
             << ") -> left: " << left[v] << ", right: " << right[v] << endl;
        if (left[v] != -1) dump_rec(left[v], space + "  ");
        if (right[v] != -1) dump_rec(right[v], space + "  ");
    }
};



/*/////////////////////////////*/
// Examples
/*/////////////////////////////*/

/* TTPC 2023 F */
struct Node {
    long long n, l, val;
    bool eps;
    Node() {}
    Node(long long n, long long l, long long e, long long v)
        : n(n), l(l), eps(e), val(v) {}
    friend ostream& operator << (ostream &s, Node node) {
        return s << "(" << node.n << ", " << node.l << ", " << node.eps
                << ", " << node.val << ")";
    }
};

void TTPC_2023_F() {
    // operators
    vector<set<char>> ops = {
        set<char>({'^'}),
        set<char>({'*'}),
        set<char>({'+'})
    };
    
    // define binary operation
    auto op = [&](char op, const Node &l, const Node &r) -> Node {
        if (op == '+') {
            vector<long long> vl({l.n, l.l, (long long)l.eps, l.val});
            vector<long long> vr({r.n, r.l, (long long)r.eps, r.val});
            return (vl > vr ? l : r);
        }
        else if (op == '*') return Node(l.n + r.n, l.l + r.l, l.eps | r.eps, 1);
        else if (op == '^') return Node(l.n * r.val, l.l * r.val, l.eps, 1);
        else return Node();
    };
    
    // define number process
    auto getnum = [&](const string &S, int &p) -> Node {
        Node res;
        if (S[p] == 'N') {
            ++p;
            return Node(1, 0, false, 1);
        } else {
            long long val = 0;
            while (S[p] >= '0' && S[p] <= '9') {
                val *= 10;
                val += (int)(S[p] - '0');
                ++p;
            }
            return Node(0, 0, false, val);
        }
    };
    
    // define function (log)
    string operator_func = "log";
    auto func = [&](const Node &node) -> Node {
        if (node.n >= 1) return Node(0, 1, false, 1);
        else return Node(0, 0, true, 0);
    };
    
    // 入力
    string S;
    cin >> S;
    Parser<Node> ps(ops, op, getnum, operator_func, func);
    auto res = ps.parse(S);
    //ps.dump();

    if (res.eps) ++res.l;
    cout << res.n << " " << res.l << endl;
}


int main() {
    TTPC_2023_F();
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

TTPC 2023 F - N^a (log N)^b

問題概要

制約

考えたこと

コード