「みんなのプロコン」D - 工場


C: 検索 - 「みんなのプロコン」 | AtCoder

解法

注文日が小さいものから貪欲に処理するのが最適である。在庫の個数を x とすると処理は次のように言い換えられる。\(w_i\)は\(i\)日目にある注文数とする。

  • 1日目(昼):\(x \to x+K\)
  • 1日目(夜):\(x \to \max(0,x-w_1) \)
  • 2日目(昼):\(x \to x+K\)
  • 2日目(夜):\(x \to \max(0,x-w_2) \)
  • ...
  • D日目(昼):\(x \to x+K\)
  • D日目(夜):\(x \to \max(0,x-w_D) \)

最終的な \(x\) は残った在庫数を表すので、実際に使った総数は \(KD-x\) である。この操作はセグメント木に載せられるため、この問題は高速に解ける。なぜ載せられるかを説明するために max-plus semiring (トロピカル半環)について書く。

max-plus semiring

左側は整数の足し算と掛け算の性質を並べたもの、右側は整数の最大値と足し算の性質を並べたものである。

\[ (a+b)+c=a+(b+c) \quad\longleftrightarrow\quad \max(\max(a,b),c)=\max(a,\max(b,c)) \]\[ (a\times b)\times c=a\times(b\times c) \quad\longleftrightarrow\quad (a+b)+c=a+(b+c) \]\[ a+0=a \quad\longleftrightarrow\quad \max(a, -\infty)=a \]\[ a\times 1=a \quad\longleftrightarrow\quad a+0=a \]\[ a(b+c)=ab+ac \quad\longleftrightarrow\quad a+\max(b,c)=\max(a+b,a+c) \]

maxを+に+を×に0を-∞書き換えてみると左側と右側はまったく同じものを表すことが分かる。こういう性質を持つものを半環 (semiring) といい、右側は特に max-plus semiring と呼ばれている。

アフィン写像

\(\mathrm{max} \to+,\,+ \to \times\) と読み替えて元の問題の操作を見直してみる。

  • 1日目(昼):\(x \to Kx\)
  • 1日目(夜):\(x \to -w_1 x+0 \)
  • 2日目(昼):\(x \to Kx\)
  • 2日目(夜):\(x \to -w_2 x+0 \)
  • ...
  • D日目(昼):\(x \to Kx\)
  • D日目(夜):\(x \to -w_D x+0 \)

すべて \(ax+b\) の形の変換である。\(ax+b\)の形の写像は合成しても\(ax+b\)の形であり、関数の合成は結合法則が成り立つからセグメント木に載る。