「みんなのプロコン」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

群・環・体は知っているだろうか。知っていれば語感から分かるだろう。環の定義を知らなくても以下の性質が成り立つことは分かる。

\[ (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) \]

(少し省略しているが)これらの性質が成り立つため\(\mathrm{max} \to+,\,+ \to \times\) と読み替えても問題ない。つまり\(\max(a,b)\)を\(a+b\)に、\(a+b\)を\(a\times b\)に書き換えても問題ない(もちろん記号の意味は変わる)。

減算が必要にならなければ環で動くアルゴリズムは大抵動く。ほぼ当たり前のことを言っているのだが 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 \)

よく見なくてもこれは線形写像である。線形写像と線形写像を合成したものは線形写像である。さらに写像の合成は結合法則が成り立つ。つまりセグメント木に載せられる。