理論

• 半環
  • min(max) を足し算、足し算をかけ算だと思う
  • 分配法則が成り立つ
    • $\max(a,b) + c = \max(a+c, b+c)$
• 通分
  • $\max(a-b, 0) = \max(a,b) -b$
    • これは $a/b + 1 = (a+b)/b$ に対応している

min-plus/max-plus 代数特有の現象

• $(a+b)^2 = a^2 + b^2$
  • クロスタームが現れない
• $a + a = a$
• tbw

応用例

• ABC351 F - Double Sum
  • $\sum_{i=1}^N \sum_{j=i+1}^N \max(A_j -A_i, 0) = \sum_{i=1}^N \sum_{j=i+1}^N (\max(A_j, A_i) - A_i)$
• 半環上の最大部分配列問題とKadane's algorithm - Ark's Blog
• 最短路問題