らての精進日記

修行をします

aoj2312:Magical Girl Sayaka-chan

解法

音程の最大値を与えるやつをKmax、最小値を与えるやつをKminとかおくと、どんな円環でもKmin→Kmaxの直線が2本あるように見える。
この問題の列のバージョンを考えると、昇順にソートするのがおそらく最適(帰納的に証明できたような気がするけど、あんまりきれいじゃなかったので、はい。そもそも直観的に自明みたいなところがある)
よって、Kmin→Kmaxとなる二本の昇順の列をつなげた円環のみを考えればよい。
これなら累積和と二次元dpでいい感じにできる。

コード