JOI2012予選4「暑い日々」のオーバーキル考察

JOI 2012-2013 予選 問題4
これの解答に触れられているものの解説されていない想定オーバーキル考察です。
「この問題に対しては,より効率の良い方法が存在する.実は,各日の服の候補のうち,Cj が最大のものまたは最小のものの 2 通りのみを考えればよいことが証明できる」ってやつです。
i日目に着る服を考えます。
i-1日目に着る服の派手さをa、i+1日目に着る服の派手さをb、i日目着る服の派手さをxとします。
f:id:eiya5498513:20170610145828p:plain
a<=x&&b<=xのとき、xが1増えるごとに差の合計は2増えるので、明らかに最大のxを取るのが最適です。
逆に、x<=a&&x<=bのとき、xが1減るごとに差の合計は2増えるので、明らかに最小のxを取るのが最適です。
xがaとbの間の時、xが1変わると、片方との差が1増え、もう片方との差が1減るので、どれを選んでも変わりません。

aとbの間のときは差が最小なので、xは最大又は最小のものをとれば良いです。