解法

問題は以下のグラフにおいて、頂点 \(0\) から頂点 \(1\) に流量 \(K\) のフローを流すときの最小のコストを求める問題と等価です。

• 頂点数 \(2 + N + M\)
• \(2 + i \to 1\), 容量 \(1\), コスト \(X_{i+1}\) (\(0 \le i < N\))
• \(0 \to 2 + N + i\), 容量 \(1\), コスト \(0\) (\(0 \le i <M\))
• \(2 + N + i \to 2 + j\), 容量 \(1\), コスト \(0\) (\(0 \le i < M, S_{i+1} - 1 \le j < E_{i+1}\))

ところがこのグラフは最悪で \(\Theta(NM)\) 本の辺を持ち、最小費用流を求めるのに Primal-Dual 法を用いると \(\Theta(KNM\log (N + M))\) 時間を使ってしまうので、制限時間に間に合いません。そこでグラフの辺の個数を減らすことを考えます。

セグメント木の要領で辺をつなぎ換えましょう。そうすれば \(O(N + M)\) 頂点で \(O(N + M \log N)\) 辺のグラフができ、その上の最小費用流は Primal-Dual 法を用いると \(O((N + M \log N)K \log (N + M))\) 時間で計算できます。具体的には以下のように辺を張ります。

• 頂点数 \(2 + M + (2^{11} - 1)\), 頂点 \(0\) から頂点 \(1\) に流量 \(K\) のフローを流す
• \(0 \to 2 + i\), 容量 \(1\), コスト \(0\) (\(0 \le i <M\))
• \(2 + i \to 2 + M + x\), 容量 \(1\), コスト \(0\) (\(0 \le i < M\), \(x\) は \(S_{i+1} - 1 \le j < E_{i+1}\) の範囲をカバーするように高々 \(20\) 頂点を選ぶ)
• \(2 + M + i \to 2 + M + 2i + j\), 容量 \(\infty\), コスト 0 (\(0 \le i < 2^{10}-1, 1 \le j \le 2\))
• \(2 + M + (2^{10} - 1) + i \to 1\), 容量 \(1\), コスト \(X_i\) (\(0 \le i < N\))

(注: 実装を簡単にするためにこの張り方ではセグメント木部分を固定サイズにしていますが、\(N\) に応じて大きさを変えれば \(O(N + M)\) 頂点 \(O(N + M \log N)\) 辺が実現できます。)

発展

問題は重み付きマトロイド交差なので、二部マッチングやフローなどのアルゴリズムのうちいずれかが使えそうです。具体的には以下の 2 個のマトロイドの交差です。

1. 大きさ \(M\)、ランク \(1\) の一様マトロイド \(N\) 個の直和。 これは各日に最大 1 個の宿題しかできないという制約に対応する。
2. 各 \(1 \le i \le M\) に対して 「\(\{1, 2, \ldots, N\}\) を台集合とし、 \(\{S_i, S_i + 1, \ldots, E_i\}\) の中から高々 1 個をとったものを独立集合とするマトロイド」の直和。これは宿題 \(i\) は \(S_i\) から \(E_i\) までにやる必要があるという制約に対応する。

実はこれは分割マトロイドとみなすこともできます。(1. が一様マトロイドの直和なので、1. と 2. の交差は 2. の各マトロイドの合併に等しいです。) マトロイドなので小さい順にとっていく貪欲が使えます。公式解説の解法はそうしています。