公式解説では \(R \leq \frac{N}{2}\) で隣り合わないようにボールを選ぶ場合と言い換えていますが、Monge グラフ上の \(d\)-辺最短路 に帰着することでも解くことができます。

まず、\(0\) 番のランプを導入し、\(A_0 = A_{N+1} = 0\) とします。 すると、問題は以下のように言い換えることができます。

先頭のランプを赤く光らせ、続くいくつかの (\(0\) 個含む) ランプを青く光らせる。 これを \(1\) 手順として丁度 \(R+1\) 回繰り返して、全てのランプを点灯させる。 \(1\) 手順でランプ \([l, r]\) を光らせた場合、\(A_l + A_r\) の報酬 を得る。 ただし \(l = r\) の場合に限り報酬は得られない。 報酬を最大化せよ。

\([l, r]\) を光らせることを \(l\) から \(r+1\) への辺と解釈し、コストの符号を反転すれば、これは \(0\) から \(N+1\) への \(R+1\) - 辺最短路です。

残る課題はこのコストが Monge 性を満たすことを示すことです。 \(ij\) 辺のコストを \(c(i, j)\) と表記することにすると、以下の式を得ます。

\[ c(i, j) = - A_i - A_{j - 1} + \begin{cases} 2A_i \quad &(i+1 = j) \\ 0 \quad &(\mathrm{otherwise}) \end{cases} \]

比較的容易に確認できる以下の事実から、\(c\) の Monge 性が導かれます。

• \((i, j) \mapsto f(i)\) は Monge
• \((i, j) \mapsto f(j)\) は Monge
• \(f(i) \geq 0\) について \((i, j) \mapsto \begin{cases} f(i) \quad &(i+1=j) \\ 0 \quad &(\mathrm{otherwise}) \end{cases}\) は Monge
• Monge な関数の和は再び Monge