clamp 関数の合成について記述します。

（clampとは：https://cpprefjp.github.io/reference/algorithm/clamp.html）

関数のグラフなどの直感を用いずに、とにかく式変形だけで合成を計算してみます。

\(\min(\max())\) 順の場合

• \(\text{clamp}(x,l,r) = \min(r,\max(l,x))\) とする。
• \(f(x) = \text{clamp}(x,l_1,r_1)\), \(g(x) = \text{clamp}(x,l_2,r_2)\) とおく。
• \(g\circ f(x) = \text{clamp}(x,l,r)\) となる \(l,r\) を求めよ。

これを計算しましょう。 \(g\) を合成することは、\(\max(l,-)\) を合成してから \(\min(r,-)\) を合成することに等しい。この手順に沿って、順に計算していきます。

\[\begin{aligned}\max(l_2,f(x)) &= \max(l_2,\min(r_1,\max(l_1,x))) \\&=\min(\max(l_2,r_1),\max(l_2,l_1,x)) \\&=\min(\max(l_2,r_1), \max(\max(l_2,l_1),x)),\\ \min(r_2,\max(l_2,f(x))) &=\min(r_2,\max(l_2,r_1),\max(\max(l_2,l_1),x)) \\ &=\min(r, \max(l, x))\\ & （ただし r = \min(r_2,\max(l_2,r_1)), l = \max(l_2,l_1)） \end{aligned}\]

となります。よって、\((l_2,r_2)\circ (l_1,r_1) = \max(l_2,l_1), \min(r_2, \max(l_2,l_1))\) という要領でパラメータを取り換えることが、関数合成に対応します。

\(\max(\min())\) 順の場合

• \(\text{clamp}(x,l,r) = \max(l,\min(r,x))\) とする。
• \(f(x) = \text{clamp}(x,l_1,r_1)\), \(g(x) = \text{clamp}(x,l_2,r_2)\) とおく。
• \(g\circ f(x) = \text{clamp}(x,l,r)\) となる \(l,r\) を求めよ。

これだと、 \(l = \max(l_2,\min(r_2,l_1)), r = \min(r_1,r_2)\) となります。 \(\text{clamp}\) 操作は \(l < r\) のときには \(\min, \max\) のどちらからやっても結果が同じですが、一般には、\(\min(r, \max(l, -))\) と \(\max(l, \min(r, -))\) の挙動は等しくなくて、合成の計算結果にも差異が確認できます。

\(\min(c, \max(b, x+a))\) の場合

解説にある関数の合成をします。

• \(f(x) = \min(c_1,\max(b_1,x+a_1))\)
• \(g(x) = \min(c_2,\max(b_2,x+a_2))\)

とします。

\[\begin{aligned} g\circ f(x) &= \min(c_2, \max(b_2, f(x)+a_2))\\ &=\min(c_2,\max(b_2,\min(c_1,\max(b_1,x+a_1))+a_2))\\ &=\min(c_2,\max(b_2,\min(c_1+a_2,\max(b_1+a_2,x+a_1+a_2))))\\ &= \min(c_2,\min(\max(b_2,c_1+a_2),\max(b_2,b_1+a_2,x+a_1+a_2)))\\ &=\min(c_2,\max(b_2,c_1+a_2),\max(b_2,b_1+a_2,x+a_1+a_2))\\ \end{aligned}\]

となるので、

\(c = \min(c_2, \max(b_2,c_1+a_2))\), \(b = \max(b_2, b_1+a_2)\), \(a = a_1+a_2\)

とすれば \(g\circ f(x) = \min(c,\max(b,x+a))\) となります。

公式解説方針による解答例：https://atcoder.jp/contests/abc196/submissions/21121201