不満度の総和は \((\sum _i S _ i) - (\sum _ i T _ i)\) です。第二項は定数なので、第一項を最小化します。以降、\(S_i\) をコストと呼びます。

以下の dp テーブルを \(i\) の降順に埋めていきます。

\[ \mathsf{dp}(i)\coloneqq\begin{aligned} & \text{ 時刻 } T_i \text{ に出荷して注文 } i { までを処理した状態から、} \\ &\text{ 注文 } i+1 { 以降を処理するコスト和の最小値.}\end{aligned} \]

\(\mathsf{dp}(i)\) の計算を考えます。いま、時刻 \(T _ i\) に出荷して注文 \(i\) までを処理した状態とします。この後の出荷時刻は \(T_i + X, T _ i + 2X, \ldots, T _ i + kX, T_j, \ldots\) のような形になっているとしてよいです。更に、時刻 \(T _ j\) における出荷で注文 \(j\) までを処理した状態となるように \(j\) を取ることが出来ます (ただし、\(T _ {N + 1} = \infty\) (十分大きな数) として \(j = N + 1\) も許すことにします)。

時刻 \(T_i + X, T _ i + 2X, \ldots\) における操作において、可能な限り多くの注文を処理することにします。このシミュレーションにおいて、時刻 \(T_i + pX\) において処理できる注文の個数を \(n\) とします。また、時刻 \(T_i + (p-1)X\) までの出荷で処理した最大の注文を \(l\) とします。

次の出荷は、以下のいずれかのタイミングです。

1. 時刻 \(T_i + pX\) に出荷する
2. \(l+n \lt j\leq l + K\) なる \(j\) を選んで時刻 \(T_j\) に (注文 \(j\) までを) 出荷する

1 の場合はそのままシミュレーションを継続することで考慮できます。ただし、 \(n=0\) の場合は出荷の意味が無いので 2 の場合だけ考慮してシミュレーションを終了してよいです。

2 の場合は、時刻 \(T_i + (p-1)X\) までのシミュレーションで計算されたコスト和を \(C\) として \(\mathsf{dp}(i) \gets \min\lbrace \mathsf{dp}(i), C + \min_{l+n\lt j\leq l+K} (T_j \cdot (j - l) + \mathsf{dp}(j))\rbrace\) と更新することで考慮できます。

以上で \(O(N^2K)\) 時間の解法が得られましたが、更に高速化できます。

ボトルネックは \(\min_{l+n\lt j\leq l+K} (T_j \cdot (j - l) + \mathsf{dp}(j))\) の計算です。これは \(l, n\) にしか依存していないことに注目して \(f(l, n) \coloneqq \min_{l+n\lt j\leq l+K} (T_j \cdot (j - l) + \mathsf{dp}(j))\) と定めます。\(f\) について、次の漸化式が成り立ちます。

\[f(l, n) = \min\lbrace T_{l+n+1}\cdot (n+1)+\mathsf{dp}(l+n+1), f(l, n+1) \rbrace.\]

この漸化式を利用すれば各 \(f(l, n)\) は全体で \(O(N^2)\) 時間で計算できます。

以上で \(O(N^2)\) 時間の解法が得られました。

計算量についての補足

シミュレーションのループが回る回数が \(O(N)\) であることは非自明ですが、これは \(n=0\) の場合にシミュレーションを終了していることが本質的です。より詳細に言えば、\(n\gt 0\) の場合に \(l\) が必ず \(1\) 以上増えますが、一方で \(l\) は高々 \(N\) であることから、ループの回数は高々 \(N\) 回であることが分かります。

実装例