ちゃっくのメモ帳

ちゃっくがメモしときたいことをメモしとくよ

ARC085 D ABS

問題
D - ABS

自分の解法はO(N^2)だが解説の方法がO(1)だった。
この解説に最初ちょっと納得できなかったのでメモ

どこで納得が行かなかったかというと「Xがa_iまで取った時,Yはa_{N-1}までとる」という部分がよくわからなかった。
というのは「Xが途中までとって,その後Yがうまく選択したらもっと低い/高い値がでるのでは?」と考えたから。。。

「Xがa_iまで取り,そのあといくつかYが取った」場合を考える
f:id:chakku000:20171112022741p:plain

こんな感じで...

もしこの結果がmax(a_N-a_{N-1},a_N-W)よりも小さくなった(つまりYが良い選択をできた)とする。
この場合,Xは前からi個を選択したのが,「Xがスコアを最大化しようとする」という前提に反しているので矛盾。よって前からi個をXが選択してスコアがより低くなることはない。

逆にXが前からi個選択して結果がmax(a_N-a_{N-1},a_N-W)よりも大きくなったとする。
この場合,Yはa_{N-1}までを選択することでスコアをa_N-a_{N-1}にすることができる。
従って,max(a_N-a_{N-1},a_N-W)を超えることはない。


これで最初に提示した疑問は解決した...はず...

(考察に漏れがあればtwitterにでもリプください)