Різдвяний вечір#365

Різдвяний вечір (Розбір)

Автор задачі:

Тимкович Олександр

Задачу підготував:

Ціцей Павло, Тимкович Олександр

Розбір написав:

Тимкович Олександр

Для зручності, зробимо індексацію з нуля, тобто a_0, a_1, \dots, a_{n-1}. Таке перетворення досить зручно в задачах з циклічними масивами, тому що ми можемо брати сусідні значення як (a_i, a_{(i+1)\bmod n}).

Нехай розчарування всіх друзів, не включаючи Сакурако, це , що можна порахувати на перед. Будемо перебирати позицію Сакурако, тобто кожну пару сусідніх друзів і Сакурако між ними. Як зміниться , якщо ми туди всунемо Сакурако? Потрібно від відняти розчарування, яке було між цією парою друзів, та додати два нові розчарування, отримані з Сакурако.