제출 #619065

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
619065		jophyyjh	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	1301 ms	28460 KiB

palindromic

/**
 * Notes during contest.
 * 
 * ------ A ------
 * In the example, (3,7,6,6) is the set of optimal pillars to select. Well, I assume
 * that the subset of pillars shall be connected in order? First, sum all costs of
 * pillars. The cost of pillars that are used will then be deducted from the total.
 * Our dp formula is:
 *        dp[k] = min( dp[i] + (h[k] - h[i])^2 - c[k])
 *              = min( (dp[i] + h[i]^2) - 2h[i] * h[k] ) + (h[k]^2 - c[k])
 * This looks like sth that can be solved with dynamic convex hull trick. IMO this
 * is like the only way to AC this problem. Unfortunately, I don't know how to code
 * one using std::set<>, nor do I know LiChao tree. Maybe I'll just head to problem
 * C.
 * [After contest]
 * First of all, I think i should've noticed the small size of |w_i| in [S2] allows
 * us to store things in a std::set<> for each value of w_i. Now, without a time
 * limit, let's try LiChao tree in impl2, and perhaps the dynamic convex hull trick
 * optimization in impl3 (notoriously difficult to code...).
 * 
 * ------ B ------
 * [S1-2] is solvable with a O(n^2) dp (Z-array + dp). I also have a hunch that we
 * can pass [S3] too (#time_limit = 10s). Oh no... I really suck at str processing
 * problems... I guess 60 points would be my limit.
 * [After contest]
 * Well, so sad that I wasn't sure about the greedy approach (which turned out to be
 * correct): each time we try to chunk off the shortest prefix & suffix of our str.
 * Why is this correct? Suppose that the greedy algo. and an optimal way of chunking
 * differs at a certain point, i.e. the greedy algo proposes to remove a prefix &
 * suffix C but in the optimal case C' is removed. Note that C would be a prefix of
 * C'. When |C| <= |C'| / 2,  C' = CXC (concat, X is a possibly empty str), so
 * (C)(X)(C) would be a better partition. This gives us the courage to deduce further
 * properties. The way i came up with proving this is to use the lemma in
 * https://cses.fi/problemset/task/1733; this shows that a prefix of
 * C'.substr(0,|C'|-|C|) is a period of C'. So just take the front portion of the
 * period, (X) and the last part of the period in C' to form a better partition.
 * 
 * ------ C ------
 * Can we score some partials here? Clearly, when Tom visits the route, only the
 * last node has pigeons, so #pigeons_Tom_meets = #last_node_in_route. OK. Let V be
 * the set of nodes in the route, so |V| <= v and
 *      #pigeons_Tom_meets = sum{ p_i : i is adjacent to at least one node in V
 *                                      or i is in V }.     (Wrong, see below)
 * We also know that #pigeons_Jerry_meets = p_i where i is the first node. This means
 * we can solve [S1-3]. Looks like DFS + dp on tree is good enough to solve the whole
 * problem!
 * --------------------------------- After contest -----------------------------------
 * I totally misunderstood the problem... Took me over an hour in the contest.. The
 * stuff above is wrong... Full solution is a standard dfs + dp on tree in O(nv).
 * 
 * Time Complexity 1: O(n * log(n))
 * Time Complexity 2: O(n * log(n))     (non-deterministic)
 * Time Complexity 3: O(n * v)
 * Implementation 2             (Full solution, str hashing)
*/
 
#include <bits/stdc++.h>
 
typedef int64_t     int_t;
typedef std::vector<int_t>  vec;
 
inline int_t pow(int_t a, int_t b, int_t mod) {
    int_t res = 1;
    while (b > 0) {
        if (b % 2 == 1)
            res = res * a % mod;
        a = a * a % mod, b /= 2;
    }
    return res;
}
 
 
// Rolling hash class. Each element of params is a pair of (p, m)
struct RH {     // rolling hash
    std::vector<vec> ps;
    std::vector<vec> pre_hash;
    RH(std::vector<vec> params, const std::string& str) {
        ps = params;
        int_t sets = params.size(), n = str.size();
        pre_hash.assign(sets, vec(n + 1));
        for (int_t s = 0; s < sets; s++) {
            int_t p = params[s][0], m = params[s][1];
            pre_hash[s][0] = 0;
            for (int_t k = 0; k < n; k++)
                pre_hash[s][k + 1] = pre_hash[s][k] * m % p + (str[k] - 'a');
        }
    }
    bool equal(int_t s1, int_t l1, int_t s2, int_t l2) {
        bool is = true;
        for (int_t s = 0; s < int_t(ps.size()) && is; s++) {
            int_t p = ps[s][0], m = ps[s][1];
            int_t h1 = pre_hash[s][s1 + l1] - pre_hash[s][s1] * pow(m, l1, p) % p;
            int_t h2 = pre_hash[s][s2 + l2] - pre_hash[s][s2] * pow(m, l2, p) % p;
            h1 = (h1 % p + p) % p, h2 = (h2 % p + p) % p;
            is &= (h1 == h2);
        }
        return is;
    }
};
 
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    int_t T;
    std::cin >> T;
    for (int_t tc = 1; tc <= T; tc++) {
        std::string str;
        std::cin >> str;
        int_t n = str.length();
 
        
        // 3 is a primitive root of 998244353 (well-known)
        RH hash({{998244353, 3}, {int_t(1e9) + 7, 5}}, str);
        int_t count = 0;
        for (int_t left = 0, right = n - 1; left <= right; ) {
            int_t len = 1;
            while (2 * len <= right - left + 1
                        && !hash.equal(left, len, right - len + 1, len)) {
                len++;
            }
            if (2 * len <= right - left + 1) {
                count += 2, left += len, right -= len;
            } else {
                count += 1;
                break;
            } 
        }
        std::cout << count << '\n';
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40