\(S\coloneqq \sum_{i=1}^N P_{i}\) とします．

グラフによる表現と DP の定式化

本問題をグラフの問題として表現します．\(0,1,\dots,N+1\) のラベルがついた \(N+2\) 頂点のグラフに，以下のように有向辺を張ります．

• 辺 \((0,j)\,(1 \leq j \leq N)\) の重みを \(\sum_{y=1}^{j-1} P_y \times (j-y)\) とする
• 辺 \((i,j)\,(1 \leq i < j \leq N)\) の重みを \(\sum_{y=i}^{j-1} P_y \times \min(y-i,j-y)\) とする
• 辺 \((i,N+1)\,(1 \leq i \leq N)\) の重みを \(\sum_{y=i}^N P_y \times (y-i)\) とする

高橋君が \(x_1,x_2,\dots,x_K\) を選んだとき，青木君が得るスコアの期待値の \(S\) 倍は，このグラフの長さ \(K+1\) のパス \(0 \to x_1 \to \dots \to x_K \to N+1\) の重みになります．青木君が得るスコアの期待値の最小値を求める問題は，このグラフでちょうど \(K+1\) 辺を使ったときの頂点 \(0\) から頂点 \(N+1\) への最短路を求める問題に帰着します．

グラフは DAG なので，この問題は DP により解くことができます． \(\mathrm{dp}[k][j]\) を，「\(k\) 本の辺を使ったときの頂点 \(0\) から頂点 \(j\) への最短路長」とします．\(\mathrm{dp}[K+1][N+1]\) が求める答えです． 遷移は次のように行います．

\[ \mathrm{dp}[k][j] = \min_{i<j} \{\mathrm{dp}[k-1][i] + c(i,j)\} \qquad (\ast) \]

ここで， \(c(i,j)\) は辺 \((i,j)\) の重みです．\(c(i,j)\) は， \(P_y\) と \(P_y \times y\) の累積和を前計算しておくことにより，クエリあたり \(O(1)\) 時間で計算できます．

ところが，この DP を素直に実装すると， \(O(N^2 K)\) 時間かかってしまいます．

コストの Monge 性と Alien DP による高速化

式 \((\ast)\) で表される DP は，遷移のコスト \(c(i,j)\) が Monge 性 と呼ばれる性質を満たすときに， Alien DP と呼ばれる手法を用いることで高速に計算できます．

コスト \(c(i,j)\) が Monge であるとは，以下の条件を満たすことです．

\[ \forall i,j,k,l,\quad 0 \leq i < j < k < l \leq N + 1 \Rightarrow c(i,l)+c(j,k) \geq c(i,k) + c(j,l) \]

本問題のコストが Monge 性を満たすことは，直感的には以下の図より理解できます．\(c(x,y)\) は \(x\) と \(y\) を結ぶ三角形領域の面積にだいたい対応していると思ってください． \(c(i,l)+c(j,k) = (A+B+C+D) + C = A+B+2C+D\), \(c(i,k)+(j,l)=(B+C)+(C+D) = B+2C+D\) となり， Monge 性の条件の不等式が成り立ちます．

次に，Alien DP を説明します．アルゴリズムの正当性などの細かい議論は以下の参考文献にゆずり，ここではアルゴリズムのみ述べます．

• noshi91 さんによる記事: Monge グラフ上の \(d\)-辺最短路長を計算するアルゴリズム

まず，関数 \(f(\lambda)\) を次のように定義します．

• コスト \(c(i,j)\) に一様に \(\lambda\) を足した上で， 使う辺の本数の制約を無視したときの頂点 \(0\) から頂点 \(N+1\) への最短路長を \(d\) とする． \(f(\lambda) \coloneqq d - \lambda (K+1)\) とする．

\(\max_{\lambda\in\mathbb{Z}} f(\lambda)\) が求める答えとなります．\(\lambda\) は辺を1本使うことに対するペナルティであり，このアルゴリズムは，使用する辺の本数がちょうど\(K+1\)本となるようなペナルティ \(\lambda\) の値を探索しているとみなせます．

\(f(\lambda)\) は \(\lambda\) に関して上に凸であること，また最適な \(\lambda\) は \(0\leq \lambda \leq 3 \max_{i,j} c(i,j) \leq 3NS\) の範囲にあることが示せます．よって，この最大化問題は，傾きの二分探索，三分探索，または黄金分割探索により \(O(\log (NS))\) 回の \(f(\lambda)\) の評価により解くことができます．この最大化問題を解く各手法は以下の記事で比較されています．

• noshi91 さんによる記事: Aliens DP における二分探索の色々

あとは，与えられた \(\lambda\) に対して \(f(\lambda)\) を高速に求めることができればよいです． これはふたたび DP によって計算することができます．遷移は以下のとおりです．

\[ \mathrm{dp}[j]=\displaystyle \min_{i < j} \{\mathrm{dp}[i] + c(i,j) + \lambda\} \qquad (\ast\ast) \]

DP の次元が一つ落ちましたが，これを素直に実装すると \(O(N^2 \log (NS))\) 時間となり，依然として間に合いません． しかし，式 \((\ast\ast)\) で表される DP は，コスト \(c(i,j)\) が Monge であるときに高速に計算できることが知られています．

Monge な辺重みを持つグラフの最短路問題

式 \((\ast\ast)\) の DP を高速に実行する方法をいくつか紹介します．解法1から3は，以下の資料で詳しく説明されています．

• tatyam さんによるスライド: Monge の手引書

解法1. 分割統治 + monotone minima \(O(N(\log N)^2)\) 時間

\((N+2)\times (N+2)\) 行列 \(A\) を，\(A_{ij}=\mathrm{dp}[j] + c(j,i) + \lambda\) として定義します．すると，DP \((\ast\ast)\) は \(A\) の各行の最小値を求める問題になります．\(c(i,j)\) が Monge であるとき，行列 \(A\) は totally monotone という性質を持ちます．Monotone minima は，totally monotone な行列の各行の最小値を \(O(N\log N)\) 時間で求めることのできるアルゴリズムです．

Monotone minima は \(A\) の要素に任意の順番でアクセスできることを要求します．ところが，今回の設定では \(\mathrm{dp}[j]\) の値を知るまで \(A_{ij}\) の値を知ることができず，\(\mathrm{dp}[j]\) の値を知るには， \(A\) の \(j\) 行目の最小値を知っている必要があります．このように，要素にアクセスできる順番に制限があるため，今回は monotone minima を直接適用することができません．

そこで，分割統治を行います．\(\mathrm{solve}(l,r)\) を，\(\mathrm{dp}[l],\dots,\mathrm{dp}[r-1]\) を求める処理として，次のようにします．

1. \(m\coloneqq \lfloor (l+r)/2\rfloor\) として， \(\mathrm{solve}(l,m)\) を再帰的に実行する．
2. \(\mathrm{dp}[l],\dots,\mathrm{dp}[m-1]\) から \(\mathrm{dp}[m],\dots,\mathrm{dp}[r-1]\) への遷移を処理する．このとき，必要な \(\mathrm{dp}\) の値はすべてわかっているから， monotone minima が使える．
3. \(\mathrm{solve}(m,r)\) を再帰的に実行する．

こうして \(O(N(\log N)^2)\) 時間のアルゴリズムが得られます．全体では \(O(N(\log N)^2 \log (NS))\) 時間となります．高速な言語であれば AC を得ることができます．

解法2. 分割統治 + SMAWK \(O(N\log N)\) 時間

解法1の monotone minima をSMAWK アルゴリズムに置き換えることで，log を1つ落とすことができます．SMAWK アルゴリズムは，totally monotone な行列の各行の最小値を \(O(N)\) 時間で求めるアルゴリズムです．ただし，SMAWK アルゴリズムは定数倍が比較的重いため，本問題の制約下では monotone minima とほとんど区別できないと思います．

解法3. LARSCH \(O(N)\) 時間

解法2をさらに工夫することにより，LARSCH アルゴリズム という \(O(N)\) 時間のアルゴリズムが得られます．LARSCH アルゴリズムの実装は少々複雑ですが，シンプルな \(O(N\log N)\) 時間の実装が noshi91 さんにより以下の記事で提案されています．時間計算量は悪化しますが，定数倍が軽いため， writer の実装では \(O(N)\) 時間の LARSCH よりも高速でした．

• noshi91 さんによる記事: 簡易版 LARSCH Algorithm

解法4. convex hull trick \(O(N\log N)\) 時間

Totally monotone 行列 \(A\) の任意の2列に対して，要素の大小関係は単調になっています．すなわち，\(A\) の \(j\) 列目を \(i\) の関数と見ると，これらの関数は互いにたかだか1回しか交わりません．

互いにたかだか1回しか交わらない関数群の最小値は，convex hull trickを応用することで求めることができます．Convex hull trickは本来，1次関数群の最小値を求めるアルゴリズムですが，関数群が互いにたかだか1回しか交わらないという性質を持てば，同様のアルゴリズムで処理することができます．2つの関数の交点を求めるときに二分探索を用いることで，\(O(N \log N)\) 時間で \((\ast\ast)\) を解くことができます．

また，一次関数群の最小値を求めるデータ構造である Li-Chao tree も同様に，互いにたかだか1点しか交わらない関数群を扱うことができます．Li-Chao tree を利用しても \(O(N \log N)\) 時間のアルゴリズムが得られます．

実装例

writer の実装では，2番目の実装が最も高速でした．

• 黄金分割探索 + 分割統治 + monotone minima
• 黄金分割探索 + 簡易版 LARSCH
• 黄金分割探索 + convex hull trick