「みんなのプロコン」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 と呼ばれている。