ここでは部分点解法の解説で登場する「\(g(x_0)=\min(x_0+p,q,-x_0+r)\) の形で表すことができます」の部分を証明します．（満点解法には直接は関係ありません．）

---

\(x_0=t\) と固定したときに貪欲に \(x_1,x_2,\ldots,x_{M-1}\) を決めていくことで生成される列を \(X(t)\) とする．

すべての \(t\) について \(k(0\leq 0\lt M-2)\) が存在して \(X(t)_k+X(t)_{k+1}\lt C_{k+1}\) となるとき

最小の \(k\) を \(k_0\) とすると \(X(t)_{k_0+1}=B_{k_0+1}\) である．

[1] \(k_0\) が偶数のとき

• \(X(t+1)_0=X(t)_0+1\)
• \(X(t+1)_1=X(t)_1-1\)
• \(X(t+1)_2=X(t)_2+1\)
• \(\vdots\)
• \(X(t+1)_{k_0}=X(t)_{k_0}+1\)
• \(X(t+1)_{k_0+1}=X(t)_{k_0+1}\)
• \(X(t+1)_{k_0+2}=X(t)_{k_0+2}\)
• \(\vdots\)
• \(X(t+1)_{M-2}=X(t)_{M-2}\)

となるため \(\sum_{i=0}^{M-2} X(t+1)_i=\sum_{i=0}^{M-2} \sum X(t)_i+1\) となる

[2] \(k_0\) が奇数のとき

• \(X(t+1)_0=X(t)_0+1\)
• \(X(t+1)_1=X(t)_1-1\)
• \(X(t+1)_2=X(t)_2+1\)
• \(\vdots\)
• \(X(t+1)_{k_0}=X(t)_{k_0}-1\)
• \(X(t+1)_{k_0+1}=X(t)_{k_0+1}\)
• \(X(t+1)_{k_0+2}=X(t)_{k_0+2}\)
• \(\vdots\)
• \(X(t+1)_{M-2}=X(t)_{M-2}\)

となるため \(\sum_{i=0}^{M-2} X(t+1)_i=\sum_{i=0}^{M-2} X(t)_i\) となる

ここで，\(X(t)\) の \(k_0\) が奇数なら \(X(t+1)\) の \(k_0\) は偶数になりえないことがわかる．すなわち \(\sum_{i=0}^{M-2} X(t+1)=\sum_{i=0}^{M-2} X(t)\) なら \(\sum_{i=0}^{M-2} X(t+2)=\sum_{i=0}^{M-2} X(t+1)\) が成り立つ．よって \(\sum_{i=0}^{M-2} X(t)=\min(t+a,b)\) の形式で書ける．

さらに \(X(0)_{M-2}=X(1)_{M-2}=\ldots=X(B_0)_{M-2}\) が成り立つから，\(X(t)_{M-1}=\min(c-t,d)\) の形で書ける．

よって \(\sum X(t)=\min(t+a,b)+\min(c-t,d)=\min(t+p,q,-t+r)\) である．

ある \(t\) が存在して，すべての \(k(0\leq 0\lt M-2)\) に対して \(X(t)_k+X(t)_{k+1}= C_{k+1}\) となるとき

そのような \(t\) は区間になっていることが分かる．最小値，最大値を \(l,r\) とする．

\(l\neq 0\) のとき，ある奇数 \(k(\leq M-2)\) が存在して \(X(l)_k=B_k\) となっている．また，\(r\neq B_0\) のとき，ある偶数 \(k(\leq M-2)\) が存在して \(X(r)_k=B_k\) となっている．

[1] \(l\leq t\leq r\) のとき

• \(X(t)_0=X(l)_0+(t-l)\)
• \(X(t)_1=X(l)_1-(t-l)\)
• \(X(t)_2=X(l)_2+(t-l)\)
• \(\vdots\)

となっており，

• \(M\) が奇数なら \(X(t)_{M-2}=X(l)_{M-2},\sum_{i=0}^{M-2} X(t)_i=\sum_{i=0}^{M-2} X(l)_i\)
• \(M\) が偶数なら \(X(t)_{M-2}=X(l)_{M-2}+(t-l),\sum_{i=0}^{M-2} X(t)_i=\sum_{i=0}^{M-2} X(l)_i+(t-l)\)

である．

[2] \(t\leq l\) のとき

上と同様の議論によって以下が成り立つ．

• \(X(t)_{M-2}=X(l)_{M-2},\sum_{i=0}^{M-2} X(t)_i=\sum_{i=0}^{M-2} X(l)_i+(t-l)\)

[3] \(t\geq r\) のとき

上と同様の議論によって以下が成り立つ．

• \(X(t)_{M-2}=X(r)_{M-2},\sum_{i=0}^{M-2} X(t)_i=\sum_{i=0}^{M-2} X(r)_i\)

\(S(t)=\sum_{i=0}^{M-2} X(t)_i, L(t)=X(t)_{M-2}\) として，これらをまとめるとい以下のようになる．

[1] \(M\) が奇数のとき

• \(t\lt l\) のとき：\(L(t+1)=L(t),S(t+1)=S(t)+1\)
• \(l\leq t\lt r\) のとき：\(L(t+1)=L(t)-1,,S(t+1)=S(t)\)
• \(r\leq t\) のとき：\(L(t+1)=L(t),S(t+1)=S(t)\)
• これらをまとめると \(S(t)=\min(S(0)+t,S(l)),X(t)_{M-1}=\min(a,b-t,\min(L(l),\max(L(l)-(t-l),L(r))))\) となり，\(S(t)+L(t)=\min(t+p,q,-t+r)\) となることが場合分けによって確認できる．

[2] \(M\) が偶数のとき

• \(t\lt l\) のとき：\(L(t+1)=L(t),S(t+1)=S(t)+1\)
• \(l\leq t\lt r\) のとき：\(L(t+1)=L(t)+1,,S(t+1)=S(t)+1\)
• \(r\leq t\) のとき：\(L(t+1)=L(t),S(t+1)=S(t)\)
• これらをまとめると \(S(t)=\min(S(0)+t,S(r)),X(t)_{M-1}=\min(a,b-t,\min(L(r),\max(L(l)+(t-l),L(l))))\) となり，\(S(t)+L(t)=\min(t+p,q,-t+r)\) となることが場合分けによって確認できる．