1657B XY Sequence - プログラム色々

この戦略が合計を最大化することを証明することも難しくありません。

矛盾することにより、最適な答えに $a_{i-1} + x \leq B$ であるが $a_{i}= a_{i-1} -yで$ あるインデックス $i$ があるとします。

$a_{j} = a_{j}−1 + x$ である最初の位置 $j \geq i$ を見つけて、iとjの間で操作を交換しましょう。

その結果、 $B \geq a_{i},a_{i+1},\cdot \cdot \cdot ,a_{j}$ と $[i,j-1$ ] からのすべての $a_{i}$ が増加しましたが、 $a_{j}$ は同じままでした。

ルールに違反することはなく、合計が増加します。結果これは矛盾します。