Конспект: экономика игры

Понятия

Граф рецептов - вещи и рёбра «из чего делается» с количеством. Общие подрецепты делают его графом без циклов, а не деревом.

Дробный рюкзак - груз можно делить; жадность по цене за единицу веса точна. Рюкзак 0/1 - целые ящики; нужна динамика или приближение.

Допуск - порог, ниже которого разница чисел с плавающей точкой считается шумом.

Дерево Фенвика по значениям - ячейка на каждое значение очков, в ней - сколько игроков его набрали. Спуск по дереву Фенвика - прыжки степеней двойки к k-му элементу за log.

Сжатие значений - встречающиеся значения сортируют и заменяют номером, чтобы дерево по значениям поместилось в память.

Что унести

РЕЦЕПТЫ
сырьё на ОДНУ штуку каждой вещи - один раз (запоминание)
столица: наивно 228 вызовов, с запоминанием 23
ромб A/B на 20 уровней: 2²¹ - 1 против 79
«из двух B» - одно ребро с весом 2, путей не удваивает
до расчёта - обход с тремя цветами: ребро в серую = круг
бревно -> кирка -> железо -> уголь -> доска -> бревно

ТРЮМ
целые ящики: t[w] = max(t[w], t[w - v] + c), w сверху вниз
11 ящиков, трюм 40: перебор 2048 наборов, динамика 338 клеток
жадность по цене за кг на ящиках: 30 вместо 48
на зерне жадность точна: 49,2
таблица ~ величина W: граммы вместо кг - в тысячу раз больше

РЫНОК
вес сделки = -log курса; выгодный круг = отрицательный цикл
Беллман-Форд, dist = 0 у всех: V · E (6 товаров - 84 проверки)
круг: V шагов по родителям, потом до повтора
1,05 · 1,05 · 1/1,1025 = 1.0, а сумма -log < 0 - допуск 10⁻¹²
точно - дробями в целых числах, без логарифмов

РЕЙТИНГ
место = 1 + n - «не больше моих очков» - префикс по ОСИ ОЧКОВ
400 игроков, 100 партий: перебор 40 000, Фенвик 1478
смена очков: -1 к старым, +1 к новым
k-й сверху = (n - k + 1)-й снизу, спуск прыжками 512, 256, ...
спортивный счёт 1, 2, 2, 4; третий в списке ≠ третье место

Ловушки джокера

Раскрытие по путям. Сложные вещи считаются секунды - число путей растёт с каждым уровнем.

Мод с кругом. Раскрытие уходит в бесконечность, сервер падает.

Жадный автопогрузчик. Игроки грузят вручную на треть выгоднее.

Таблица по граммам. Трюм считается секундами и сотнями мегабайт.

Сравнение логарифмов без допуска. Монитор экономики кричит о кругах, которых нет.

Фенвик по игрокам. Отвечает на вопрос, который никому не нужен.

Место без договорённости. Двое с равными очками видят второе и третье место.