C - Index × A(Continuous ver.) 解説 by rsk0315


\(A\) を 0-indexed で扱い、\(l\) から始まる長さ \(M\) の連続部分列のスコア(問題で要求されている最大化したい値)を考えます。半開区間として扱い、終端位置を \(r = l+M\) とします。

\(\sum\) の中に \(i\) ではなく \(l\) が含まれていると累積和で高速化しにくい(後述)ので、それを分離するのを意識して変形します。

\[ \begin{aligned} f(l, r) &= \sum_{i=l}^{r-1}\, (i-l+1) \times A_i \\ &= \sum_{i=l}^{r-1}\, (i+1)\times A_i - l\cdot\sum_{i=l}^{r-1} A_i. \end{aligned} \]

ここで、\(S_0(r) = \sum_{i=0}^{r-1} A_i\)\(S_1(r) = \sum_{i=0}^{r-1}\, (i+1)\times A_i\) とおくと、

\[ f(l, r) = (S_1(r) - S_1(l))-l\cdot(S_0(r) - S_0(l)) \]

とできます。よって、求めたい値

\[ \max_{M\le i\le N} f(i-M, i) \]

\(O(N)\) 時間で計算できるようになります。

提出 #34581466


このように、高速化しやすい形を意識して式変形すると見通しがよくなる気がします。 累積和を用いて \(f(l, r)\)\(O(1)\) 時間で求められるので、「クエリ形式で与えられる区間 \([l, r)\) について \(f(l, r)\) を出力せよ」のような問題にも答えられます。

実装の際に 0-indexed・半開区間で扱うのがやりやすいことが多いので、(特に添字の +1/-1 が関わる場合は)考察の段階でも 0-indexed にして式変形などを行う方がよいでしょう。


bonus: \(M\) が与えられない場合の問題、すなわち任意の区間における最大値 \(\max_{0\le l\le r\le N} f(l, r)\)\(1\le N\le 2\cdot 10^5\) で求めてみましょう。難易度は F 問題くらいだと思います。ジャッジ

解法の概要 CHT (convex hull trick) という手法があります。これを適用できる形を意識して式変形しましょう。

\(\sum\) の中に \(i\)(ループ変数)ではなく \(l\)(区間の始端)が入っていると累積和で高速化しにくいという話について。

\(f(l, r) = \sum_{i=l}^{r-1} g(i)\) という関数を累積和で高速化するときは、\(S(r) = \sum_{i=0}^{r-1} g(i)\) という関数を作る(始端を適当な箇所に固定する)ことで、\(f(l, r) = S(r) - S(l)\) と変形します。場合によっては終端を固定しますが今回の本筋ではありません。

このとき、(解説冒頭の式のように)始端である \(l\)\(\sum\) の中に含まれている(\(\sum_{i=l}^{r-1} g(i, l)\) など)と、「(終端が変わるのはいいが)始端が変わると前計算した \(S\) が使えなくなってしまう」という状況になり、\(\Theta(n^2)\) 個の前計算テーブルが必要になってしまいます。これでは愚直と同じです。

そこで、たとえば

\[ f(l, r) = \sum_{i=l}^{r-1} g_0(i) + c(l)\cdot\sum_{i=l}^{r-1} g_1(i) \]

のように、各々の \(\sum\) の中から \(l\) を分離することで、それぞれを \(S(r)-S(l)\) の形にできるようになり、\(\Theta(n)\) 個のテーブルで済むようになります。

問題によっては、和に分解するのではなく

\[ f(l, r) = \left(\sum_{i=l}^{r-1} g_0(i)\right)\times\left(\sum_{i=l}^{r-1} g_1(i)\right) \]

のように積に分解するケースもあるかもしれません。

いずれにせよ、無闇に式変形するのではなく、(累積和やその他の勉強したテクを用いて)高速化するにはどういう形であればいいかを意識して式変形するのがよいでしょう。考察前の段階ではどうしてそのテクで高速化できなくて、どうすれば解消するかを意識するということです。

投稿日時:
最終更新: