AtCoder Regular Contest 077 E - guruguru

お題箱より。

後半は公式解説と少し違う方法になっています。

解法

お気に入りで節約できる回数を定式化する

ある1つの $i$ に対する $a_{i}$ から $a_{i+1}$ への移動を考えます。まず簡単のため、 $a_{i} \lt a_{i+1}$ と仮定しておきます。移動元と移動先をそれぞれ $s_{i} = a_{i}, t_{i} = a_{i+1}$ と書くことにします。

お気に入りボタンを使わずに $s_{i}$ から $t_{i}$ に移動するボタン回数は $t_{i}-s_{i}$ です。ここで「 $t_{i}-s_{i}$ と比べて、お気に入りボタンがもし値 $x$ に設定されていたら回数をどれだけ節約できるか？」という値をそれぞれの $x$ について考えましょう。この値を $f_{i}(x)$ と書くことにします。

これは以下のように、 $s_{i} + 2 \le x \le t_{i}$ の範囲において $1, 2, ...$ という等差数列になり、他は0になります。

f:id:betrue12:20191019155240p:plain

ただし $a_{i} \gt a_{i+1}$ のときは途中で明るさがループします。これを扱うのは面倒なので、「ループするときは2周回す」テクニックを使います。

$a_{i} \gt a_{i+1}$ のときは移動先 $t_{i}$ は2周目にあると考えて、 $s_{i} = a_{i}, t_{i} = a_{i+1} + m$ とします。そして $f_{i}(x)$ も2周分、つまり $1 \le x \le 2m$ の範囲で値を持つことにします。このときお気に入りが $x$ に設定されている時の節約回数は、1周目と2周目を合わせて $f_{i}(x) + f_{i}(x+m)$ と求めればよいです。

これを $n-1$ 回の移動について全て足したもの、つまり $\sum_{i}f_{i}(x) + \sum_{i}f_{i}(x+m)$ が「お気に入りを $x$ に設定したときに、お気に入りを全く使わない時に比べて節約できる合計回数」です。この最大値を、お気に入りを全く使わない時の合計回数 $\sum_{i} (t_{i} - s_{i})$ から引いたものが答えになります。