Добрый день. Не мог бы кто-нибудь подсказать решение задачи G с neerc 2007. Заранее спасибо.
Условия: http://neerc.ifmo.ru/past/2007.html
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | awoo | 158 |
4 | cry | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | maroonrk | 152 |
Добрый день. Не мог бы кто-нибудь подсказать решение задачи G с neerc 2007. Заранее спасибо.
Название |
---|
Зафиксируем левую и правую границы LBord, RBord. Теперь для каждого человека посчитаем вероятность того, что, если он отдаст токен налево, токен вернётся к нему, не выйдя за левую границу. Обозначим для i-го человека эту вероятность Lret[i][LBord][RBord]. Обозначим вероятность отдать токен налево L[i], а направо - R[i]. Тогда там сумма бесконечной геометрической прогрессии:
Lret[i][LBord][RBord] = R[i-1] / (1 - L[i-1] * Lret[i-1][LBord][RBord])
Для крайнего слева Lret[LBord][LBord][RBord] = 0. Для остальных хорошо считается динамикой слева направо.
Аналогично введём Rret[i][LBord][RBord]. Тогда вероятность для позиции, заданной левой границей, правой границей и положением токена перейти саму в себя равна:
Pret[Token][LBord][RBord] = L[Token] * Lret[Token][LBord][RBord] + R[Token] * Rret[Token][LBord][RBord].
Когда мы посчитаем эту вспомогательную динамику, начнём считать основную: она будет идти по отрезкам с фиксированными границами и токеном либо ровно на левой либо ровно на правой границе. Обозначим матрицу этой динамики P[B][LBord][RBord]. B = 0 для левой, B = 1 для правой.
Тогда:
P[1][LBord][RBord + 1] = P[1][LBord][RBord] * R[RBord] / (1 - Pret[RBord][LBord][RBord]) + P[0][LBord][RBord] * (1 - Pret[LBord][LBord][RBord])
Вспомогательная динамика пройдёт за О(n^3). Основная - за О(n^2). Надеюсь, что нигде не лажанул.