Блог пользователя dyatkovskiy

Автор dyatkovskiy, история, 5 лет назад, По-русски

Здесь пара комментариев (для себя и других) касательно разбора задачи 1238E сделанного пользователями awoo и Roms. Я там не сразу понял — как получается конечная формула для перебора символа.

( заморочился и написал код с трассировкой (см. под катом) )

Давайте вначале придумаем общую суммарную формулу, которая отразит количество всех перемещений, и потом, используя нисходящий подход прийдем к решению.

Двигаясь вправо, для каждого символа $$$s$$$, имеющего на клавиатуре позицию $$$x$$$ будем учитывать все перемещения между ним и символами слева. Так, очевидно, мы в итоге учтем все перемещения. Этот подсчет можно выразить вот так:

$$$cnt = \sum_{x=1}^{n} \sum_{y=1}^{x-1} cnt_{xy} (x - y)$$$

Здесь $$$x$$$ и $$$y$$$ — это координаты символов на клавиатуре. А $$$cnt_{xy}$$$ — это соответсвенно общее количество переходов между символами на клавиатуре $$$s_x$$$ и $$$s_y$$$ .

(да — обозначения немного отличаются, но зато формула получается более компактная).

Так как же получается то славное выражение, которое приведено awoo в конце разбора для задачи 1238E?

Надо немного поиграть с символами и попереставлять значки сумм.

Для начала раскроем скобки $$$x-y$$$:

$$$cnt = \sum_{x=1}^{n} \sum_{y=1}^{x-1} cnt_{xy} x - \sum_{x=1}^{n} \sum_{y=1}^{x-1} cnt_{xy} y$$$

Без знания предметной области формулу уже не упроситить. Но мы знаем, что:

  • $$$cnt_{xy}=cnt_{yx}$$$
  • Обозначения "x" и "y" — на самом деле локальные и фиксированы только внутри той или иной суммы.
  • В выражении, состоящем только из сумм и разностей, идущие подряд значки сумм ($$$\sum$$$) мы можем менять местами (главное тут — не облажаться с теми самыми локальными переменными).

Поэтому, давайте внимательно взглянем на правую часть формулы:

$$$\sum_{x=1}^{n} \sum_{y=1}^{x-1} cnt_{xy} y$$$

Мы ее можем переписать вот так:

$$$\sum_{y=1}^{n} \sum_{x=1}^{y-1} cnt_{xy} x$$$

(просто поменяли названия переменных).

А теперь задумаемся о смысле левой и правой частей все той же формулы:

Вот это:

$$$\sum_{x=1}^{n} \sum_{y=1}^{x-1} cnt_{xy} x$$$

На самом деле перебирает все возможные символы $$$x$$$ и все возможные символы $$$y$$$, которые стоят слева от $$$x$$$.

А вот это:

$$$\sum_{y=1}^{n} \sum_{x=1}^{y-1} cnt_{xy} x$$$

На самом деле перебирает все возможные символы $$$x$$$ и все возможные символы $$$y$$$, которые стоят (!) справа от $$$x$$$.

Savvy?

Перегруппировав слагаемые (убрав старые операторы сумм и введя новые), получим вот такую формулу:

$$$cnt = \sum_x ( \sum_{y \in mask} cnt_{xy} x - \sum_{y \notin mask} cnt_{xy} x ) $$$

Внезапно, все сказанное в legacy разборе обретает смысл. Для каждого отдельно взятого $$$x$$$ мы приходим к той самой, славной, формуле

$$$cnt_x = \sum_{y \in mask} cnt_{xy} x - \sum_{y \notin mask} cnt_{xy} x $$$

(ну, только там $$$x$$$ обозначался как $$$pos_x$$$, $$$cnt_{xy}$$$ при переходе от координат к самим символам — не поменяет смысла).

Свой вариант решения
  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится