🤔
期待値 DP の漸化式などで現れる方程式の解法

2025/05/10に公開
 概要\forall i, a_i < 0 のとき、x に関する方程式

  \min_i (a_i x + b_i) = 0
がちょうど 1 つの解 \alpha をもち、各 a_i x + b_i = 0 の解 \alpha_i = -\frac{b_i}{a_i} を用いて

  \alpha = \min_i \alpha_i
と表せることを示す。
また、同値な命題として \forall i, a_i' < 1 のとき、x に関する方程式

  x = \min_i (a_i' x + b_i)
がちょうど 1 つの解 \alpha をもち、各 x = a_i' x + b_i の解 \alpha_i = \frac{b_i}{1 - a'_i} を用いて

  \alpha = \min_i \alpha_i
と表せることを示す。
さらに \max についても同様の命題が成り立つことを示す。
その結果から、ABC 350 E - Toward 0 において期待値 DP の漸化式を素朴にたてたあと、機械的な式変形により 公式解説 と同じ式が得られることを示す。

 動機!証明に関係ないので読み飛ばしてもかまいません。
AtCoder Beginner Contest で期待値 DP が出題されたとき、よくある漸化式の形として

  E[i] = \sum_j P_{i, j} ( W_{i, j} + E[j])
や

  E[i] = \min_j P_{i, j} ( W_{i, j} + E[j])
のようなものを考えると思います。各記号は以下のイメージです。

i: 状態

j: i から 1 ステップで遷移できる状態

P_{i, j}: i から j に遷移する確率

W_{i, j}: i から j に遷移するのかかるコスト

E[i]: i から終了状態に遷移するまでにかかるコストの期待値
ここで、j = i となりうる場合 (状態 i が自己ループの遷移をもつ場合) には右辺にも E[i] が含まれます。このとき、うまく DP の計算をするために E[i] を左辺に移項したくなると思います。
\sum の場合は単に E[i] の項を左辺に移項すればよいですが、\min (, や \max) の場合はその変形が少し非自明のように感じます (\min の中身を勝手にばらして移項していいのかなど)。
先日、ABC 350 E - Toward 0 の解説 を読んだところ、
Xに関する方程式X=\min(c,pX+q)はp<1のとき常にちょうど1つの解を持ちます（証明略）
との記述があったので、おそらく \min についても移項することで解決できそうだと思いました。

本記事はその一般化として以下の方程式を考えます。

 問題設定f_i(x) を x の一次関数 f_i (x) = a_i x + b_i とする。

ただし、a_i < 0, b_i は任意の実数とする。
x に関する方程式

  \min_i f_i(x) = \min_i ( a_i x + b_i ) = 0
がちょうど 1 つの解 \alpha をもち、

  \alpha = \min_i \alpha_i  
と表せることを示す。ただし、\alpha_i は各 f_i(x) = 0 の解とする。

つまり、\min の中身を取り出してそれぞれ方程式を解き、各解の \min をとれば元の方程式の解となるということである。
証明は以下の 2 ステップで行う。
Step 1: 解が存在すれば高々 1 つ
Step 2: 解が存在する
1, 2 を合わせると解がちょうど 1 つ存在し、その解が \alpha = \min_i \alpha_i と表せることが示せる。

 Step 1: 解が存在すれば高々 1 つグラフによる直感的な証明
y = 0, y = \min_i f_i(x) の交点が存在すると仮定して、その交点の 1 つの x 座標を任意に \beta_1 とおく。

このとき、\min の定義から \min_i f_i(\beta_1) = f_j(\beta_1) となる j が存在する。

\beta_1 は y = 0 と y = f_j(x) = a_j x + b_j の交点の x 座標でもある。
\beta_1 < x の範囲では、

a_j < 0 なので、y = f_j(x) < 0

\min の性質から y = \min_i f_i(x) \le f_j(x) < 0
すなわち、y = \min_i f_i(x) は \beta_1 < x の範囲で y = 0 と交わることはない。

\beta_1 は任意にとっているので、どのように選んでも y = 0, y = \min_i f_i(x) の交点は高々 1 つしか存在しないことがわかる。
上記のイメージをもとに、以下の証明では 2 個目の交点 \beta_2 の存在も仮定して矛盾を導くという背理法で示している。
背理法で示す。すなわち、\min_i f_i(x) = 0 の相異なる解が 2 つ以上存在すると仮定して矛盾を導く。
解を任意に 2 つとり、\beta_1, \beta_2 (\beta_i < \beta_2) とおく。

このとき、

  \begin{aligned}
    \min_i f_i(\beta_1) &= 0 \\
    \min_i f_i(\beta_2) &= 0 \quad \ldots (1)
  \end{aligned}
\min の定義から \min_i f_i(\beta_1) = f_j(\beta_1) となる j が存在する。

ゆえに、

  \min_i f_i(\beta_1) = f_j(\beta_1) = a_j \beta_1 + b_j = 0 \ldots (2)
が成り立つ。このとき、x = \beta_2 における f_j(x) の値に着目すると、

  \begin{aligned}
    f_j (\beta_2) &= a_j \beta_2 + b_j \\
    &= a_j \beta_2 + (- a_j \beta_1) \quad (\because (2))\\
    &= a_j (\beta_2 - \beta_1) \\
    &< 0  \quad (\because a_j < 0, \beta_1 < \beta_2) \ \ldots (3)
  \end{aligned}
さらに x = \beta_2 における \min_i f_i(x) の値に着目すると、

  \begin{aligned}
    \min_i f_i(\beta_2) &\le f_j(\beta_2) \quad (\because \min \textrm{の性質})\\
    & < 0 \quad (\because (3))
  \end{aligned}
となり、(1) に矛盾する。

 Step 2: 解が存在するグラフによる直感的な証明

矛盾が起こるケース
\min_i \alpha_i = \alpha_j となる j が存在する。

x = \alpha_j において \min の性質から \min_i f_i(x) \le f_j(x) が成り立つ。
\min_i f_i(x) = f_j(x) の場合、\alpha_j が元の方程式 \min_i f_i(x) = 0 の解となる。
\min_i f_i(x) < f_j(x) の場合、x = \alpha_j において f_k(x) < f_j(x) となる k が存在するということになるが、これはありえないことを示す。

y = f_k(x) = a_k x + b_k は a_k < 0 なので、y = 0 と y = f_k(x) の交点の x 座標 \alpha_k は \alpha_j より小さくなる。

これは \min_i \alpha_i = \alpha_j に矛盾する。
\min の定義から \min_i \alpha_i = \alpha_j となる j が存在する。

また、\alpha_j の定義から f_j (\alpha_j) = 0 が成り立つ。
さらに、\min の性質から \min_i f_i (\alpha_j) \le f_j (\alpha_j) が成り立つ。この不等式の等号が成立するかどうかで場合分けを行う。ただし、成り立たない場合は矛盾が生じることから空虚に真であることを示す。

 \min_i f_i (\alpha_j) = f_j (\alpha_j) の場合
  \min_i f_i (\alpha_j) = f_j(\alpha_j) = 0
が成り立つので、\alpha_j は \min_i f_i(x) = 0 の解である。

 \min_i f_i (\alpha_j) < f_j (\alpha_j) の場合\min の定義から \min_i f_i(\alpha_j) = f_k(\alpha_j) となるような k が存在する。

このとき、

  f_k(\alpha_j) = \min_i f_i (\alpha_j) < f_j (\alpha_j) = 0 \ldots (4)
\alpha_j, \alpha_k はそれぞれ f_j(x) = a_j x + b_j = 0, f_k(x) = a_k x + b_k = 0 の解なので、

  \alpha_j = -\frac{b_j}{a_j}, \alpha_k = -\frac{b_k}{a_k} \ldots (5)
が成り立つ。
ここで、

  \begin{aligned}
    f_k(\alpha_j) 
      &= a_k \alpha_j + b_k 
      = a_k \left( -\frac{b_j}{a_j} \right) + b_k \quad (\because (5))\\
      &= \frac{a_j b_k - a_k b_j}{a_j}
  \end{aligned}
と (4) より

  f_k(\alpha_j) = \frac{a_j b_k - a_k b_j}{a_j} < 0 \ldots (6)
が成り立つ。
\alpha_k, \alpha_j の大小関係を調べると、

  \begin{aligned}
    \alpha_k - \alpha_j 
    &= -\frac{b_k}{a_k} - \left (-\frac{b_j}{a_j} \right) 
    = \frac{  a_k b_j - a_j b_k }{a_k a_j}
    = -\frac{1}{a_k} \cdot \frac{ a_j b_k - a_k b_j }{a_j}
     < 0 \quad (\because (6), a_k < 0) \\
    \therefore \alpha_k &< \alpha_j
  \end{aligned}
これは \min_i \alpha_i = \alpha_j に矛盾するため、このケースは空虚に真である。

 同値な命題
 x = \min_i (a'_i x + b_i) \ (a'_i < 1) の解\min_i (a_i x + b_i) = 0 の両辺に x を足すと

  \begin{aligned}
    x + \min_i (a_i x + b_i) &= x \\
    \therefore x &= \min_i \left ( (1 + a_i) x + b_i \right )
  \end{aligned}
a_i < 0 なので、a'_i = 1 + a_i とおくと a'_i < 1 であり、方程式は以下の形になる。

  x = \min_i (a'_i x + b_i)
(期待値の最小化を行う期待値 DP の漸化式はこの形式になることがある。)
この解 \alpha は

  \alpha = \min_i \left( - \frac{b_i}{a_i} \right) = \min_i \left( \frac{b_i}{1 - a'_i} \right)
と表せる。

 \max_i (a'_i x + b'_i) = 0 \ (a'_i > 0) の解\min_i (a_i x + b_i) = 0 の両辺に -1 をかけると

  \begin{aligned}
    -\min_i (a_i x + b_i) &= 0 \\
    \therefore \max_i (- a_i x - b_i) &= 0
  \end{aligned}
a'_i = - a_i, b'_i = -b_i とおくと、a_i < 0 なので a'_i > 0 であり、方程式は以下の形になる。

  \max_i (a'_i x + b'_i) = 0
この解 \alpha は

  \alpha = \min_i \left( -\frac{b_i}{a_i} \right) = \min_i \left( -\frac{b'_i}{a_i'} \right)
と表せる。

 x = \max_i (a''_i x + b'_i) \ (a'_i > 0) の解\max_i (a'_i x + b'_i) = 0 の両辺に x を足すと

  \begin{aligned}
    x + \max_i (a'_i x + b'_i) &= x \\
    \therefore x &= \max_i \left( (1 + a'_i) x + b'_i \right)
  \end{aligned}
a''_i = 1 + a'_i とおくと、a'_i > 0 より a''_i > 1 であり、方程式は以下の形になる。

  x = \max_i (a''_i x + b'_i)
この解 \alpha は

  \alpha = \min_i \left( -\frac{b'_i}{a'_i} \right) = \min_i \left( \frac{b'_i}{1 - a''_i} \right)
と表せる。

 例: ABC 350 E - Toward 0ABC 350 E - Toward 0 において、E[N] を「N を 0 にするまでに払う必要がある金額の期待値の最小値」とおく。
素朴に立式すると

  E[N] = \min
    \left( 
      X + E\left [ \left \lfloor \frac N A \right \rfloor \right ],
      Y + \sum_{b=1}^6 \left( 
        \frac 1 6 E \left [ \left \lfloor \frac N b \right \rfloor \right ] 
      \right)
  \right)
となる。

E\left [ \left \lfloor \frac N A \right \rfloor \right ] は、2 \le A より E[N] と異なる。

E \left [ \left \lfloor \frac N b \right \rfloor \right ] は、b = 1 の場合に E[N] となる。
上式を E[N] に関する方程式と見て、x = \min_i (a'_i x + b_i) \ (a'_i < 1) の解 の方法で解を求める。

a_1 = 0, b_1 = X + E\left [ \left \lfloor \frac N A \right \rfloor \right ], a_2 = \frac 1 6, b_2 = Y + \sum_{b=2}^6 \left( \frac 1 6 E \left [ \left \lfloor \frac N b \right \rfloor \right ] \right) とおくと、a_i < 1 であり、

  E[N] = \min_{i \in \left \{ 1, 2 \right \}} \left( a_i E[N] + b_i \right)
とかけるので、

  \begin{aligned}
    E[N] 
      &= \min_{i \in \left \{ 1, 2 \right \}} \frac{b_i}{1 - a_i} 
      = \min \left( b_1, \frac 6 5 b_2 \right)  \\
      &= \min \left (
    X + E\left [ \left \lfloor \frac N A \right \rfloor \right ],
    \frac 6 5 Y + \frac 1 5 \sum_{b=2}^6 \left( 
      E \left [ \left \lfloor \frac N b \right \rfloor \right ] 
    \right)
  \right ) 
  \end{aligned}
となり、ABC 350 E - Toward 0 の解説 と同じ式が得られた。
期待値 DP では a_i にあたる部分は確率となり、基本的には a_i < 1 が満たされるので上記のやり方で解が求まる。(a_i = 1 の場合は別途考慮)
期待値 DP の漸化式などで現れる方程式の解法

概要

動機

問題設定

Step 1: 解が存在すれば高々 1 つ

Step 2: 解が存在する

$\min_i f_i (\alpha_j) = f_j (\alpha_j)$ の場合

$\min_i f_i (\alpha_j) < f_j (\alpha_j)$ の場合

同値な命題

$x = \min_i (a'_i x + b_i) \ (a'_i < 1)$ の解

$\max_i (a'_i x + b'_i) = 0 \ (a'_i > 0)$ の解

$x = \max_i (a''_i x + b'_i) \ (a'_i > 0)$ の解

例: ABC 350 E - Toward 0

Discussion
