ARC085 D ABS
問題
D - ABS
自分の解法はだが解説の方法がだった。
この解説に最初ちょっと納得できなかったのでメモ
どこで納得が行かなかったかというと「Xがまで取った時,Yはまでとる」という部分がよくわからなかった。
というのは「Xが途中までとって,その後Yがうまく選択したらもっと低い/高い値がでるのでは?」と考えたから。。。
「Xがまで取り,そのあといくつかYが取った」場合を考える
こんな感じで...
もしこの結果がよりも小さくなった(つまりYが良い選択をできた)とする。
この場合,Xは前からi個を選択したのが,「Xがスコアを最大化しようとする」という前提に反しているので矛盾。よって前からi個をXが選択してスコアがより低くなることはない。
逆にXが前からi個選択して結果がよりも大きくなったとする。
この場合,Yはまでを選択することでスコアをにすることができる。
従って,を超えることはない。
これで最初に提示した疑問は解決した...はず...
(考察に漏れがあればtwitterにでもリプください)
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者: 渡部有隆
- 出版社/メーカー: マイナビ出版
- 発売日: 2015/01/30
- メディア: Kindle版
- この商品を含むブログを見る