Домівка > C++, Комбінаторика > Розв’язання задачі MappingABC з TopCoder

Розв’язання задачі MappingABC з TopCoder

Тут я розгляну розв’язок задачі MappingABC з TopCoder. Це задача з першого дивізіону другого рівня складності, тому вона вимагає певний рівень учасника для розв’язання.

Основне спостереження, яке допомагає в розв’язанні – це те, що для того, щоб порахувати всі прийнятні рядки ми можемо розбити рядок на три підрядки: до першого A – [0, FA], між першим A і останнім C – [FA, LC] і після останнього C – [LC,t.size()-1]. Ми рахуємо лише ті рядки в яких у [FA, LC] трапляється B.

Введемо дві множини для позначення символів які трапляються лише зовні [FA, LC] і інші, відповідно \mathcal O і \mathcal I. Тоді кількість прийнятних рядків така:
\prod_{s\in \mathcal O}\mbox{bitcount}(s) + \Big( \prod_{s\in \mathcal I}\mbox{bitcount}(s) - \prod_{s\in \mathcal I}\mbox{bitcount}(s \& 5) \Big).

Дивись коментарі в сирцевому коді для подальших роз’яснень.

class MappingABC
{
public:
    // Обмеження
    //    - кількість елементів між 3 і 3000
    //    - кожен елемент між 1 і 3000
    static int countStrings(const std::vector<int>& t);
};

constexpr int kMaxPositions = 3000 + 1;
constexpr int kMaxElement = 3000 + 1;

// Рахує кількість бітів у масці
int bits_cnt(int mask) {
    int count = 0;
    while (mask > 0) {
        if ((mask & 1) == 1) count++;
        mask >>= 1;
    }
    return count;
}

// Кожна маска містить стільки 1-бітів скільки різних символів вона допускає
enum Mask {
    None = 0,
    A = 1,
    B = 2,
    AB =  A | B,
    C = 4,
    AC = A | C,
    BC = B | C,
    ABC = A | B | C,
    Count = ABC + 1,
};
Mask operator&(Mask a, Mask b) {
    return Mask(underlying_type_t<Mask>(a) & underlying_type_t<Mask>(b));
}
Mask& operator&=(Mask& a, Mask b) { a = a & b; return a; }

int MappingABC::countStrings(const vector<int>& t) {
    constexpr int mod = 1000000007;
    const int N = (int)t.size();
    // Скільки разів у рядку зустрічається кожен символ
    int occurs[kMaxElement] = {};
    for (auto s : t) ++occurs[s];

    // Якщо маска зустрічається k разів,
    // то вона допускає (кількість 1-бітів)^k комбінацій.
    // Заздалегідь обчислюємо степені
    int pmask[(int)Mask::Count][kMaxPositions];
    for (int m = 0; m < Mask::Count; ++m) {
        pmask[m][0] = 1;
        const int bc = bits_cnt(m);
        for (int j = 1; j < kMaxPositions; ++j)
            pmask[m][j] = (long long)(pmask[m][j - 1]) * bc % mod;
    }

    long long ret = 0;
    for (int a = 0; a < N; ++a) {
        // Кількості символів з певною маскою поза і в [FA, LC] -
        // зовнішні, внутрішні
        int out[Mask::Count] = {};
        int in[Mask::Count] = {};
        Mask masks[kMaxElement] = {}; // Маска, що відповідає символу
        int aoccurs[kMaxPositions] = {}; // Скільки разів ми побачили символ
                                         // на цій ітерації
        // Спочатку всі варіанти можливі
        for (int i = 0; i < kMaxElement; ++i) masks[i] = Mask::ABC;

        // Символи в [0, FA] можуть набувати лише значення B і C
        for (int i = 0; i < a; ++i) { masks[t[i]] = Mask::BC; ++aoccurs[t[i]]; }
        // Якщо це не перше входження цього символу, він не може бути першим A
        if (aoccurs[t[a]] != 0) continue;
        masks[t[a]] = Mask::A; ++aoccurs[t[a]];

        // Якщо на цій ітерації ми вже побачили цей символ стільки разів скільки
        // він трапляється в рядку, то він точно зовнішній
        for (int i = 0; i < kMaxElement; ++i) if (occurs[i] != 0) {
            if (aoccurs[i] == occurs[i]) ++out[masks[i]];
            else ++in[masks[i]]; // Не гарантовано, що він внутрішній,
                                 // але ми виправимо потім
        }

        // Проходимо по всіх можливих позиціях для C
        for (int c = N - 1; c > a + 1; --c) {
            const int tc = t[c];
            // Не рахуємо цю маску, бо все одно цей символ має лише значення C
            --in[masks[tc]];
            // Перевіряємо чи бува ми не зустрічали цей символ правіше
            if (masks[tc] & Mask::C) {
                // Кількість комбінацій зовнішніх символів
                long long ret_out = 1;
                // Кількість всіх комбінацій внутрішніх символів
                long long ret_in = 1;
                // Кількість комбінацій внутрішніх символів, що не містять B
                long long ret_in_ex = 1;
                for (int m = 1; m < Mask::Count; ++m) {
                    ret_out = ret_out * pmask[m][out[m]] % mod;
                    ret_in = ret_in * pmask[m][in[m]] % mod;
                    ret_in_ex = ret_in_ex * pmask[m & Mask::AC][in[m]] % mod;
                }
                ret += ret_out * (ret_in - ret_in_ex) % mod;
                // Відтепер цей символ не може мати значення C
                masks[tc] &= Mask::AB;
            }

            ++aoccurs[tc];
            if (aoccurs[tc] == occurs[tc]) ++out[masks[tc]];
            else ++in[masks[tc]];
        }
    }

    return ret % mod;
}
Advertisements
Категорії:C++, Комбінаторика Позначки:, ,
  1. Коментарів ще немає.
  1. No trackbacks yet.

Залишити відповідь

Заповніть поля нижче або авторизуйтесь клікнувши по іконці

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: